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$ Algorithms asymptotic-notation recurrence-relation + – SomnathKayal asked Apr 14, 2016 retagged Jun 4, 2017 by Arjun SomnathKayal 863 views answer comment Share Follow See 1 comment See all 1 1 comment reply Himanshu1 commented Apr 18, 2016 reply Follow Share O( n * (1.5) n ) 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes Upper bound will be $O\left ( n.\left ( \frac{3}{2} \right )^{n} \right )$ Shyam Singh 1 answered May 12, 2016 Shyam Singh 1 comment Share Follow See all 0 reply Please log in or register to add a comment.
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) sethi answered Apr 15, 2016 sethi comment Share Follow See all 0 reply Please log in or register to add a comment.