edited by
5,845 views
22 votes
22 votes

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?

  1. $\text{P-II, Q-III, R-IV, S-I}$
  2. $\text{P-IV, Q-III, R-I, S-II}$
  3. $\text{P-III, Q-II, R-IV, S-I}$
  4. $\text{P-IV, Q-II, R-I, S-III}$
edited by

5 Answers

Best answer
8 votes
8 votes

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.$  

selected by
0 votes
0 votes
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
Answer:

Related questions

41 votes
41 votes
1 answer
1
Ishrat Jahan asked Nov 2, 2014
5,505 views
Let $H_1, H_2, H_3,$ ... be harmonic numbers. Then, for $n \in Z^+$, $\sum_{j=1}^{n} H_j$ can be expressed as$nH_{n+1} - (n + 1)$$(n + 1)H_n - n$$nH_n - n$$(n + 1) H_{n+...