Register

GO Classes DPP | GATE CS, DA | Algorithms | Asymptotic Complexity

126 views

1 Answer

0 0 votes

Given:

$T(n)=T(n/5)+T(4n/5)+O(n)$

At each level of the recursion tree, the total size of all subproblems is:

$n/5+4n/5=n$

Therefore, the total work at each level is $O(n)$.

The longest branch repeatedly reduces the problem size by a factor of $4/5$, so the recursion tree has $O(\log n)$ levels.

Thus:

$T(n)=O(n)\cdot O(\log n)$

$\boxed{T(n)=O(n\log n)}$

Answer: B

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

3 3 votes
1 1 answer
134
134 views
GO Classes asked Jul 29
134 views
GO Classes DPP | GATE CS, DA | Algorithms | Asymptotic Complexity
Solve the recurrence:$T(n) = T(n-2) + \log n$Assume $T(n)$ is constant for small $n$.$O(\log n)$ $O(n)$ $O(n\log n)$ $O(n^2)$
2 2 votes
1 1 answer
110
110 views
GO Classes asked Jul 29
110 views
GO Classes DPP | GATE CS, DA | Algorithms | Asymptotic Complexity
For $T(n,n)$, consider:$T(x,c) = \Theta(x)$ for $c \leq 2$$T(x,y) = \Theta(x) + S(x,y/2)$$S(c,y) = \Theta(y)$ for $c \leq 2$$S(x,y) = \Theta(y) + T(x/2,y)$What is the asy...
2 2 votes
1 1 answer
95
95 views
GO Classes asked Jul 29
95 views
GO Classes DPP | GATE CS, DA | Algorithms | Asymptotic Complexity
For $T(n,n)$, consider:$T(x,c) = \Theta(x)$ for $c \leq 2$$T(c,y) = \Theta(y)$ for $c \leq 2$$T(x,y) = \Theta(x) + T(x,y/2)$ What is the asymptotic complexity of $T(n,n)$...
2 2 votes
1 1 answer
110
110 views
GO Classes asked Jul 29
110 views
GO Classes DPP | GATE CS, DA | Algorithms | Asymptotic Complexity
For $T(n,n)$, consider:$T(x,c) = \Theta(x)$ for $c \leq 2$$T(c,y) = \Theta(y)$ for $c \leq 2$$T(x,y) = \Theta(x+y) + T(x/2,y/2)$What is the asymptotic complexity of $T(n,...