GATE IT 2004 | Question: 57

Question

Consider a list of recursive algorithms and a list of recurrence relations as shown below. Each recurrence relation corresponds to exactly one algorithm and is used to derive the time complexity of the algorithm.

$$\begin{array}{|l|l|l|l|}\hline \text{}  &  \textbf{Recursive Algorithm } & \text{} & \textbf{Recurrence Relation} \\\hline  \text{P} & \text{Binary search} & \text{l.} & \text{$T(n) = T(n-k) +T(k) +cn$} \\\hline  \text{Q.} & \text{Merge sort} &\text{ll.}  &  \text{$T(n) = 2T(n-1) + 1$ }\\\hline\text{R.}  &  \text{Quick sort}& \text{lll.}  &  \text{$T(n) = 2T(n/2) + cn$}\\\hline \text{S.}  &  \text{Tower of Hanoi} & \text{lV.}  &  \text{$T(n) = T(n/2) + 1$} \\\hline \end{array}$$

Which of the following is the correct match between the algorithms and their recurrence relations?

• A. $\text{P-II, Q-III, R-IV, S-I}$
• B. $\text{P-IV, Q-III, R-I, S-II}$
• C. $\text{P-III, Q-II, R-IV, S-I}$
• D. $\text{P-IV, Q-II, R-I, S-III}$

Answer 1

Answer is B.

For binary search on $n$ elements we pick a path of $n/2$ elements after doing a single comparison $(O(1))$ and discard the remaining $n/2$ elements So, $T(n) = T(n/2) + 1.$

For merge sort on $n$ elements we divide the array into two equal parts containing $n/2$ elements, recursively merge sort them and finally merges the $2$ arrays in $O(n)$ time. So, $T(n) = 2T(n/2) + cn.$

For quick sort on $n$ elements we split the array based on the position of the pivot. If pivot happens to be the $k+1^{th}$ element in the sorted array, we do a recursive call using $k$ elements and $n-k-1$ elements and we need $O(n)$ time to decide the position of the pivot. So, $T(n) = T(n-k-1) + T(k) + cn.$ (A $“-1”$ is missing in the question option).

For Tower of Hanoi using $n$ disks, to position the first disk we have to replace $n-1$ disks two times. To place the remaining disks we have to recursively solve the problem thus giving $T(n) = 2T(n-1) + 1.$  

Comments

@Arjun Sir’s comment, if anyone has doubt

​​​​​​R.    Quick sort

if we take (K+1)th element as pivot.

then, k elements on left and (n-k-1) elements on right of pivot (considering sorted array)

n-k-1 we get because ,

we have elements from (k+2) , (k+3) ,……………………..n  on the right of pivot.

---

ASNR1010

To exclude k right?

---

@Arjun @gatecse  @Kabir5454 sir

I am not able to understand quick sort here.

“If pivot happens to be the k+1th element in the sorted array…...” 

---

@GateOverflow04 It simply means that in an array of $n$ elements, if $k+1$^th element is the pivot, then we will have $k$ elements on left side and $n-k-1$ elements on right side.

Then we need to call recursively quicksort on $(k)$ elements and quicksort on $(n-k-1)$ elements. They take $T(k)$ and $T(n-k-1)$ times respectively. Also to find the pivot we need $O(n)$ time [because partition algo takes $O(n)$ time].

Hence the time complexity of quick sort is : $T(n) = T(n-k-1) + T(k) + cn.$

Answer 2

Answer is B.

Answer 3

Ans: B

P-IV, Q-III, R-I, S-II

Answer 4

Answer : B

P-IV, Q-III, R-1, S-II

Quick sort: T(k) for the kth element(smallest or greatest), T(n-k) for the rest of the element, n for partition.

T(n) = T(n-k) + T(k) + cn

Merge sort: T(n) = 2T(n/2) + cn

Binary search: T(n) = T(n/2) + 1

because in binary search mid element take O(1) time and after finding mid only apply binary search on one side(either left side or right side whichever required).

Tower of Hanoi: T(n) = 2T(n-1) + 1