PA of Algorithms Q81

81Consider 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.

List-I (Recursive Algorithm)		List-II (Recurrence Relation)
P.	Binary search	I.	T(n) = T(n - k) + T(k) + cn
Q.	Merge sort	II.	T(n) = 2T(n - 1) + 1
R.	Quick sort	III.	T(n) = 2T(n/2) + cn
S.	Tower of Hanoi	IV.	T(n) = T(n/2) + 1

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

	P	Q	R	S
(a)	II	III	IV	I
(b)	IV	III	I	II
(c)	III	II	IV	I
(d)	IV	II	I	III

Option : B

Explanation :

Algorithm	Recurrence Relation
P. Binary Search	IV. T (n) = T (n/2) + 1
Q. Merge Sort	III. T (n) = 2T (n/2) + cn
R. Quick Sort	I. T (n) = T (n-k) + T (K)
S. Tower of Hanoi	II T (n) = 2T (n-1)+1

Forgot your password?

I agree with the Terms.