GATE CSE 2017 | Set 2 | Question: 03

Question

Match the algorithms with their time complexities:

$$\begin{array}{|l|l|}\hline \textbf{Algorithms}  &  \textbf{Time Complexity} \\\hline  \text{P. Tower of Hanoi with $n$ disks} & \text{i. $\Theta (n^2)$} \\\hline  \text{Q. Binary Search given $n$ sorted numbers} & \text{ii. $\Theta (n \log n)$} \\\hline \text{R. Heap sort given $n$ numbers at the worst case} & \text{iii. $\Theta (2^n)$} \\\hline \text{S. Addition of two $n\times n$ matrices} & \text{iv. $\Theta (\log n)$} \\\hline \end{array}$$

• A. $P\rightarrow (iii) \quad  Q \rightarrow(iv) \quad r \rightarrow(i)   \quad S \rightarrow(ii)$
• B. $P\rightarrow (iv) \quad  Q \rightarrow(iii) \quad  r \rightarrow(i) \quad  S\rightarrow(ii)$
• C. $P\rightarrow (iii) \quad  Q \rightarrow(iv) \quad r \rightarrow(ii) \quad S\rightarrow(i)$
• D. $P\rightarrow (iv) \quad  Q \rightarrow(iii)\quad  r \rightarrow(ii) \quad  S\rightarrow(i)$

Comments

is it in syllaus

Answer 1

→ Tower of Hanoi with n disks takes θ(2n) time
It is a mathematical game or puzzle.
It consists of three rods and a number of disks of different sizes, which can slide onto any rod.
The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack.
3. No disk may be placed on top of a smaller disk.
With 3 disks, the puzzle can be solved in 7 moves.
The minimal number of moves required to solve a Tower of Hanoi puzzle is 2n-1, where n is the number of disks.
→ Binary Search given n sorted numbers takes Ɵ(log2 n)
→ Heap sort given n numbers of the worst case takes Ɵ(n log n)
→ Addition of two n×n matrices takes Ɵ(n2)

Answer 2

P. Towers of Hanoi → Recurrence: T(n) = 2T(n-1) + 1 → Θ(2ⁿ) → (iii)

Q. Binary Search → Halving each time → Θ(log n) → (iv)

R. Heap Sort worst case → Build heap O(n) + n extractions each O(log n) → Θ(n log n) → (ii)

S. Addition of two n×n matrices → Must visit all n² elements → Θ(n²) → (i)