G5BADS'06 informal coursework 1

  1. What is the running time growth function of this algorithm?
    binarySearch(int[] arr, int value){
          int left  = 0;
          int right  = arr.length - 1;
          int middle;
          while (right >= left){
              middle  = (left+right)/2;
              if (value == arr[middle]) return true;
              else {
                 if (value < arr[middle]) right  = middle-1;
                 else left  = middle+1;
              }
          }
          return false;
       }
    
    What is the worst case time complexity of this algorithm (in terms of big-Oh)?
  2. Prove that 7 n 2 + 10n + log2n is in O(n2) and
  3. Prove that 7 n 2 + 10n + log2n is not in O(n).
  4. Prove that O(logan) = O(logbn).