Register

GO Classes DPP | Algorithm |UGC NET

467 views
1 1 vote

Arrange the following recurrence relations in increasing order of their time capacity.

(A) $\mathrm{T}(\mathrm{n})=\mathrm{T}(\mathrm{n} / 2)+1$

(B) $\mathrm{T}(\mathrm{n})=2 \mathrm{~T}(\mathrm{n} / 2)+\mathrm{n}$

(C) $T(\mathrm{n})=3 \mathrm{~T}(\mathrm{n} / 3)+\mathrm{n}$

(D) $\mathrm{T}(\mathrm{n})=2 \mathrm{~T}(\mathrm{n} / 2)+\sqrt{\mathrm{n}}$

(E) $\mathrm{T}(\mathrm{n})=\mathrm{T}(\mathrm{n}-1)+1$

Choose the correct answer from the options given below :

  1. $\mathrm{(E), (A), (B), (D), (C)}$
     
  2. $\mathrm{(A), (E), (D), (B), (C)}$
     
  3. $(\mathrm{E}),(\mathrm{A}),(\mathrm{D}),(\mathrm{B}),(\mathrm{C})$
     
  4. $\mathrm{(A), (B), (D), (E), (C)}$

4 Answers

1 1 vote
all of them can be solved by just using master's theorem .

the largest is C which is theta( n.logn)
then B = C  = theta( n.logn)
then D = theta (N)... just use master theorem case ( polynomially greater)
E = D = O(N)
1 1 vote
$(A.)$ - Binary Search - $O(logn)$

$(B.)$ - Merge Sort - $O(nlogn)$

$(C.)$ - Similar to Merge Sort - $O(nlogn)$

$(D.)$ - Cant find a intuitive example, Take help of Master Theorem- $O(n)$

$(E.)$ - Simple Recursive addition - $O(n)$

 

$A<E=D<B=C$
Voting & Accepting an answer helps improve the community
← Previous · GO Classes DPP | Alg...Next → · #2013 pyq
← Previous in category · GO Classes DPP | Alg...Next in category → · GO Classes DPP | Alg...
Position:
Show:

Related questions

2 2 votes
3 3 answers
504
504 views
GO Classes asked Sep 11, 2025
504 views
GO Classes DPP | Algorithm |Asymtotic analysis
Which of the following is not time complexity of the following code:(O represents big-oh) for (i=1 to n): // Some constant time operation,O(1) // Then a loop that runs lo...
2 2 votes
2 2 answers
429
429 views
GO Classes asked Sep 11, 2025
429 views
GO Classes DPP | Algorithm |sorting
If the array $A$ contains elements $25,40,23,7,54,78$ and $2$ in that order, The element at $3^{\text {rd }}$ position of the array after $3^{\text {rd }}$ pass of insert...
1 1 vote
2 2 answers
447
447 views
GO Classes asked Sep 11, 2025
447 views
GO Classes DPP | Algorithm |ISRO
G is an undirected graph with vertex set ( $\mathrm{v} 1, \mathrm{v} 2, \mathrm{v3}, \mathrm{v4}, \mathrm{v5}, \mathrm{v6}, \mathrm{v7}$ ) and edge set [ $\mathrm{v} 1 \m...
2 2 votes
2 2 answers
308
308 views
GO Classes asked Sep 11, 2025
308 views
GO Classes DPP | Algorithm |ISRO
A Huffman tree is constructed for the following data: $[A, B, C, D, E]$ with frequency $\{0.17$, $0.11,0.24,0.33$ and $0.15$} respectively. $1000001101$ is decoded asBACE...