search
Log In
0 votes
32 views
Use a recursion tree to give an asymptotically tight solution to the recurrence $T(n) =T(n-a)+T(a)+cn$, where $a\geq 1$ and $c >0$ are constants.
in Algorithms 32 views

Please log in or register to answer this question.

Related questions

0 votes
0 answers
1
27 views
Use a recursion tree to give an asymptotically tight solution to the recurrence $T(n)=T(\alpha n) +T((1-\alpha)n) +cn$,where $\alpha$ is a constant in the range $0<\alpha<1$ and $c>0$ is also constant.
asked Apr 5, 2019 in Algorithms akash.dinkar12 27 views
0 votes
0 answers
2
22 views
Draw the recursion tree for $T(n)=4T(\lfloor n/2\rfloor) +cn$, where $c$ is a constant,and provide a tight asymptotic bound on its solution. Verify your bound by the substitution method.
asked Apr 5, 2019 in Algorithms akash.dinkar12 22 views
0 votes
0 answers
3
24 views
Argue that the solution to the recurrence $T(n)=T(n/3)+T(2n/3)+cn$,where $c$ is a constant, is $\Omega(n\lg n)$ by appealing to a recursion tree.
asked Apr 5, 2019 in Algorithms akash.dinkar12 24 views
0 votes
0 answers
4
55 views
Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n)=T(n-1)+T(n/2) +n$.Use the substitution method to verify your answer.
asked Apr 5, 2019 in Algorithms akash.dinkar12 55 views
...