Suppose function call parameter passing costs constant time

Suppose function call parameter passing costs constant time, independent of the size of the structure being passed. Give a recurrence for worst case running time of the recursive Binary Search function in terms of n, the size of the search array. Assume n is a power of 2. Solve the recurrence. Give a recurrence for worst case running time of the recursive Merge Sort function in terms of n, the size of the array being sorted. Solve the recurrence.

Solution

A recurrence relation for an algorithm defines the run time of the algorithm on an input size in terms of smaller input sizes.

Recurrence relation of Binary Search

A typical recursive function for Binary search on a sorted array A[] of numbers works by dividing the array into half and then limiting the search to the left half of the array if the search element is less than the mid element of the array. Otherwise the search is on the right half of the array. This recursive search goes on each time dividing the sub array into half .

The recursive implementation of Binary search looks like the one given below and returns the index of the search element X if found and 0 if not found.

BINARY SEARCH(A,X,low,high)

mid=(low+high)/2

if X = A[mid] then

index := mid

else if X < A[mid] and low < mid then

call BINARY_SEARCH(A,X, low, mid-1)

else if X > A[mid] and mid < high then

call BINARY_SEARCH(A,X, mid+1, high)

else index := 0

Initial call to function with array of size n would look like BINARY_SEARCH(A,X,1,n)

In order to find out the recurrence relation, we need to understand that in worst case there are atleast 3 comparisons ( = , < and > ) of X with A[mid] before moving on to next recursive call on half the input array i.e n/2 size. So the recurrence relation can be written as

T(n)=T(n/2)+3 for n>=2 and

T(1) = 3 for n=1

Now let\'s solve the recurrence relation.

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

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

T(n/4)=T(n/8)+3

.....

T(2)=T(1)+3

T(1)=3

adding both the sides we get

T(n)+T(n/2)+T(n/4)+.....+T(2)+T(1)=T(n/2)+T(n/4)+T(n/8)+......T(2)+T(1)+( 3+ 3+3.....+3)

The number of 3s on right side is log N times. Cancelling out equal terms on both sides , we are left with

T(n)=3 log N

Hence we can T(n)=O(log n)

Therefore running time T(n) is O(log N)

Recurrence

T(n)=T(n/2)+3 for n>=2

Base case

T(1) = 3

Recurrence solution

T(n) is of O(log n)

Recurrence relation of Merge sort

A typical recursive Merge Sort algorithm sorts the input array of numbers by breaking it into 2 half and sorting the left and right subarrays separately and then merging these 2 subarrays into one.

A recursive implementation for Merge sort for an array A with indicess start and end. Looks like

Output would be sorted array A.

MERGE_SORT(A,start,end)

if(start<end)

mid=(start+end)/2

call MERGE_SORT(A,start,mid)

call MERGE_SORT(A,m+1,end)

COMBINE the sorted subarray A[start].....A[mid] and A[mid+1] .....A[end] into a single array A

end if

Now let\'s get the recurrence relation. For input size of n such that n=2^k (2 power k), in worst case during COMBINE there are atleast n comparisons needed to determine the ordering in merged array. Since this algorithm works by dividing input in half, and working on 2 halves, we can write recurrence relation as

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

T(1)=1

Now let\'s solve the recurrence

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

=2*[2*T(n/4)+n/2]+n by substituting for T(n/2)

=4*T(n/4)+n+n

=4*[2*T(n/8)+n/4]+2n by subsiting for T(n/4)

=.8*T(n/8)+8n

.........

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

=2^k+kn since n=2^k or k=log N

=n+n log n

=O( n log n)

Therefore running time of Merge sort is O(n log n)

Recurrence

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

Base case

T(1) = 1

Recurrence solution

T(n) is of O(n log n)

Recurrence	T(n)=T(n/2)+3 for n>=2
Base case	T(1) = 3
Recurrence solution	T(n) is of O(log n)