Match the algorithms with their time complexities: Algorithm Time complexity (P) Towers of Hanoi with n disks (i) Θ (n 2 ) (Q) Binary search given n sorted numbers (ii) Θ (n log n) (R) Heap sort given n numbers at the worst case (iii) Θ (2 n) (S) Addition of two n × n matrices (iv) Θ (log n)

Correct Answer is : P – (iii), Q – (iv), R – (ii), S – (i)

P – (iii), Q – (iv), R – (i), S – (ii)

P – (iv), Q – (iii), R – (i), S – (ii)

P – (iii), Q – (iv), R – (ii), S – (i)

P – (iv), Q – (iii), R – (ii), S – (i)

GATE Computer Science (CS) 2017 Shift 2 Solved Paper

Question : 13 of 65

Marks: +1, -0

Match the algorithms with their time complexities:

	Algorithm		Time complexity
(P)	Towers of Hanoi with n disks	(i)	Θ (n²)
(Q)	Binary search given n sorted numbers	(ii)	Θ (n log n)
(R)	Heap sort given n numbers at the worst case	(iii)	Θ (2ⁿ⁾
(S)	Addition of two n × n matrices	(iv)	Θ (log n)

Go to Question:

Prev Question

Next Question