Question

Determine the order of complexity for the following algorithm:

function(int n) {
int l, u, m;
   l=0; u= n-1;
   while (l<u) {
       m= (l+u)/2;
       if (a[m] < x) l= m+1;
       else if (a[m] >x) u=m-1;
           else return “found”
   }
   return (“not found”);
}

Answer 1

Each time in the while loop the size is getting decreased by 2
and in each time it is taking some constant time c.

So, Recurrence relation is
T(n) = T(n/2) + c

Solving Recurrence relation
T(n) = T(n/2) + c
     = T(n/4) + c + c
     = T(n/8) + c + c + c
     ......
     ......
     ......
     = T(n/n) + c + .... + c + c + c [log(n) +1 terms]
     = c + c + .... + c + c + c [log(n) +1 terms]
     = clog(n)
     = O(logn)

O(logn)