2,600 views
2 votes
2 votes
Use the recursion tree to determine a good asymptotic upper bound on the recurrence T(n)=T(n-1)+T($\frac{n}{2}$)+n. Use substitution method to verify the answer.

1 Answer

Related questions

0 votes
0 votes
1 answer
2
akash.dinkar12 asked Apr 5, 2019
276 views
Can the master method be applied to the recurrence $T(n)=4T(n/2)+n^2\ lg\ n$ ?Why or why not? Give an asymptotic upper bound for this recurrence.
0 votes
0 votes
0 answers
3
akash.dinkar12 asked Apr 5, 2019
245 views
Use the master method to show that the solution to the binary-search recurrence $T(n)=T(n/2) + \Theta(1)$ is $T(n)=\Theta(lg\ n)$.