edited by
6,788 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)$
edited by

7 Answers

Best answer
31 votes
31 votes

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)  

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
Answer:

Related questions

39 votes
39 votes
5 answers
1
Madhav asked Feb 14, 2017
9,518 views
Match the following according to input (from the left column) to the compiler phase (in the right column) that processes it:$$\begin{array}{|l|l|}\hline \text{P. Syntax t...
26 votes
26 votes
3 answers
2
khushtak asked Feb 14, 2017
5,766 views
Match the following:$$\begin{array}{|ll|ll|}\hline P. & \text{static char var ;} & \text{i.} & \text{Sequence of memory locations to store addresses} \\\hline Q. & \text...
25 votes
25 votes
7 answers
3
khushtak asked Feb 14, 2017
6,938 views
Consider the following table:$$\begin{array}{|l|}\hline \textbf {Algorithms} & \textbf{Design Paradigms } & \\\hline \text{P. Kruskal} & \text{i. Divide and Conquer} \...
50 votes
50 votes
7 answers
4
Madhav asked Feb 14, 2017
24,330 views
Consider the following C functionint fun(int n) { int i, j; for(i=1; i<=n; i++) { for (j=1; j<n; j+=i) { printf("%d %d", i, j); } } }Time complexity of $fun$ in terms of ...