edited by
6,790 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

0 votes
0 votes
→ 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:

Related questions

39 votes
39 votes
5 answers
1
Madhav asked Feb 14, 2017
9,520 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,768 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,347 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 ...