GATE 2017 CS (CS2) – Question 13

Algorithms · Asymptotic Analysis and Time/Space Complexity · 1 mark · Multiple choice

Match (P) Towers of Hanoi with n disks, (Q) binary search on n sorted numbers, (R) worst-case heap sort on n numbers, (S) addition of two n×n matrices, with (i) Θ(n²), (ii) Θ(n log n), (iii) Θ(2ⁿ), (iv) Θ(log n).

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–ii,R–iii,S–i

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) P–iii,Q–iv,R–ii,S–i

Explanation

Hanoi uses 2ⁿ−1 moves, Θ(2ⁿ). Binary search halves its search interval, Θ(log n). Heap sort extracts n maxima at logarithmic cost, Θ(n log n). Matrix addition visits n² entries, Θ(n²). Therefore P–iii,Q–iv,R–ii,S–i, C.

More Asymptotic Analysis and Time/Space Complexity questions

GATE 2017 CS (CS2) Q40 – T(n)=2T( n)+1 for n>2, and T(n)=2 for 0<n≤2. Find its asymptotic order.
GATE 2017 CS (CS2) Q48 – Find the time complexity.
GATE 2012 CS (CS1) Q15 – Find the worst-case search time in a balanced BST with n2n elements.
GATE 2012 CS (CS1) Q28 – W(n) and A(n) are worst-case and average running times on inputs of size n. Which always…
GATE 2013 CS (CS1) Q40 – How many elements can heap sort sort in ( n) time?
GATE 2013 CS (CS1) Q41 – What is the asymptotic return value, rather than running time?

All Asymptotic Analysis and Time/Space Complexity questions →