in Algorithms edited by
6,758 views
25 votes
25 votes

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}$$

  1. $P\rightarrow (iii) \quad  Q \rightarrow(iv) \quad r \rightarrow(i)   \quad S \rightarrow(ii)$
  2. $P\rightarrow (iv) \quad  Q \rightarrow(iii) \quad  r \rightarrow(i) \quad  S\rightarrow(ii)$
  3. $P\rightarrow (iii) \quad  Q \rightarrow(iv) \quad r \rightarrow(ii) \quad S\rightarrow(i)$
  4. $P\rightarrow (iv) \quad  Q \rightarrow(iii)\quad  r \rightarrow(ii) \quad  S\rightarrow(i)$
in Algorithms edited by
6.8k views

7 Answers

31 votes
31 votes
Best answer

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.

edited by
10 votes
10 votes

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

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 nxn matrices = T(n)= 2T(n/2)+n2 = Ɵ (n2)  

3 Comments

how did you come up with the recurrence relation for matrix addition,can you explain?
0
0
Can u explain the recurrence relation for the matrix ??
0
0
5 votes
5 votes

We know the recurrence raltion of tower of hanoi is

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

solving it we get theta (2n)

and all others are direct 

Heap sort->nlogn 

Binary search->logn

matrix addition ->n2

so C is correct answer here

4 votes
4 votes
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})$
edited by
by
Answer:

Related questions