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

$$\begin{array}{|l|l|l|l|}\hline \text{}  &  \textbf{Recursive Algorithm } & \text{} & \textbf{Recurrence Relation} \\\hline  \text{P} & \text{Binary search} & \text{IV.} &  T(n) = T(n/2) + 1 \\\hline  \text{Q.} & \text{Merge sort} & \text{llI.}  & T(n) = 2T(n/2) + cn \\\hline\text{R.}  &  \text{Quick sort}& \text{I.}  & T(n) = T(n-k) +T(k) +cn \\\hline \text{S.}  &  \text{Tower of Hanoi} & \text{lI.}  & T(n) = 2T(n-1) + 1  \\\hline \end{array}$$
$\therefore P – IV, Q – III, R – I, S – II$

So, the correct answer is $(B).$