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

According to the recurrence relation of the time complexity of Tower of Hanoi, $T(n) = 2 T( n-1 ) +1,$  we get it is  $\Theta(2^n)$

Now, heap sort worst case time complexity is $\Theta(n \log n)$

Binary Search to search an element given $n$ sorted numbers is $\Theta(\log n)$

Addition of two $n\times n$ matrices is  $\Theta(n^2)$

So, C is correct answer here.

Answer 2

P) Towers of honoi with $n$ disks $= T(n)= 2T(n-1)+1 = Ɵ (2^n) .$

Q) Binary Search given $n$ numbers $n$ sorted numbers $= T(n)= T(n/2)+1 = Ɵ (logn)$

R) Heap sort given $n$ numbers at the worst case$ = T(n)= 2T(n/2)+n = Ɵ (nlogn)$

S) Addition of two $n × n$ matrices $= T(n)= 2T(n/2)+n2 = Ɵ (n^2)  $

Comments

how did you come up with the recurrence relation for matrix addition,can you explain?

---

Can u explain the recurrence relation for the matrix ??

---

https://www.geeksforgeeks.org/program-addition-two-matrices/

Answer 3

We know the recurrence raltion of tower of hanoi is

T(n) = 2 T( n-1 ) +1

solving it we get theta (2ⁿ)

and all others are direct 

Heap sort->nlogn 

Binary search->logn

matrix addition ->n²

so C is correct answer here

Answer 4

P. tower of hanoi $O(2^{n})$

Q. binary search $O(log n)$

R. heap sort $O(n logn)$

S. addition of two matrix $O(n^{2})$

Answer 5

c option is correct

Answer 6

1. P→→ (iii) Q →→(iv) r →→(ii) S→→(i)