198 views

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
1
akash.dinkar12 asked Apr 5, 2019
194 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...
0 votes
0 votes
0 answers
2
akash.dinkar12 asked Apr 5, 2019
165 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 subs...
0 votes
0 votes
0 answers
3
akash.dinkar12 asked Apr 5, 2019
166 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.
0 votes
0 votes
0 answers
4
akash.dinkar12 asked Apr 5, 2019
371 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.