Question

Use recursion function to derive computation time for Binary Search by drawing a recursion tree diagram and using algebra calculation.

Answer 1

Here is the solution for your problem -

Binary search is a divide and conquer algorithm. So binary search reduces the search space to half in every call.

Given A is an array of n elements where elements are in sorted order.
Let the key element to be searched be x.
If x is present in the array we will return its position else return -1.

Let us start with low=0 and high = n-1. In each step we will find mid value in the array and compare it with key element.

there are 3 cases possible -

1) If key=A[mid], we will return mid

2) If key<A[mid] , we will discard all elemnts in right half including the midlle element , and make our new high as mid-1.

3) If key>A[mid], we will discard all the elements present in left half including the middle element, and make our new low as mid+1.

We will repeat the above three steps until we found the key element of our low becomes greater than high .
Algorithm-
Algorithm binary_search(int A[], int low, int high, int x)
{

if(low>high) { return -1; }
mid=(low+high)/2;
if(x==A[mid])
return mid;
else if(x < A[mid])
binary_search(A, low, mid-1, x);
else binary_search(A, mid+1, high, x);
}

Let n be the number of elements in array.
Let T(n) be the time taken to search a value in list of n elements.
BEST CASE TIME COMPLEXITY-
T(n)=1 for n=1
for best case time complexity will be O(1).

AVERAGE OR WORST CASE-
Every time the recursive function is called with half the number of elements than the previous call.
Each time we will make one comparision and divide the list to half i.e. n elements to n/2 elements.
T(n)= 1 + T(n/2) for n>1
Here T(n/2) is the time taken to search in an array of n/2 elements.

T(n) = 1 + T(n/2)
= 1 + [1 + T(n/4) ]
= 2 + T(n/4)
= 2 + [1 + T(n/8)]
= 3 + T(n/8)
= 3 + T(n/ 2^3) and so on

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

So computation time for binary serach will be O(log_{​​​​2}​​​​​​ n)