Recurrence Relation of BST

Question

Let T (n) be the number of comparisons needed in a binary search of a list of n elements. What is the recurrence relation? Explain.

1) T(n) = T(n/2) + 2

2) T(n) = T(n/2) + 1

Answer 1

See the following part of the code for binary search:

if(A[mid]==num)

{

    return mid;

}

else if(A[mid]<num)

{

   return bsearch(A,low,mid-1);

}

else

{

    return bsearch (A,mid+1,high);

}

 

Here 2 comparison in worst case for every recursive call

T(n)=T(n/2) +2