title: Algorithm time complexity with binary search
body: <p>I am trying to figure out what the time complexity of my algorithm is, I have algorithm with binary search, which is in general O(log n), I know. But I search between two constants, namely x=1 and x = 2^31 - 1 (size of integer). I think that in the worst case my time complexity is log2(2^31) = 31, so binary search takes 31 steps in the worst case. However every step in binary search I call a function, which has O(n) runtime (just one loop of the size of the input). Will my algorithm simply be of order O(31n)=O(n)?</p>
  
  <p>The input of my algorithm: a key, two arrays a and b of size n.</p>
  
  <p>In code it will look something like this:</p>
  
  <pre><code>    binarySearch(key, a, b)
      min = 0, max = 2^31 - 1
      mid = (min + max) / 2
      while (min&lt;=max) { 
          x = function(mid, a, b); //this function has O(n)
          if (x==key) {
              return mid;
          } else if (x &lt; key) { 
              min = mid + 1
          } else {
              max = mid - 1
          }
          mid = (min + max) / 2
      }
      return KEY_NOT_FOUND
  </code></pre>
  
  <p>I just want to be sure, please if you come with a time complexity (reduced ones) explain your answer. </p>