retagged by
863 views
3 votes
3 votes
It's a question from Cormen book Exercise 4.4-5 and is described like this:

Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n)=T(n-1)+T(\frac{n}{2})+n$
retagged by

2 Answers

1 votes
1 votes
it think it will be O(n^2)..bcozT(n/2)+n->time complexity is O(n) by master's theorem and let O(n)=Cn where C is any constant

Now T(n)=T(n-1)+Cn

if we solve through recursion tree it will give O(n^2)