a better guess on upper bound

Question

It's a question from 《introduction to algorithms》whose number is 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(n/2) + n.Use the substitution method to verify your answer.

I found it is difficult to me to calculate the recursion tree's recurrence. The answer I gave

Math.pow(2,n)

seems too loose.Maybe there is some better guess existed.Thanks for any help.

Answer 1

Hope I did no mistakes :)

let's A(n)=T(n/2)+n

0. T(n)=T(n-1)+A(n)=T(n-2)+A(n-1)+A(n)=...=A(1)+A(2)+...+A(n)
   T(n)=sum[1..n]A(n)
   T(n)=sum[i=1..n]T(i/2)+sum[i=1..n]i

assuming n/2 is integer division, T(n/2)=T((n+1)/2) for even n, so the first sum consists of two equal halves: T(1)+T(1)+T(2)+T(2)+...

1. T(n)=2*sum[1..n/2]T(i)+n*(n-1)/2

since T(n)<=T(m) for every n<=m

2. T(n)<=n*T(n/2)+n*(n-1)/2

since T(n/2)>=n/2>=(n-1)/2

3. T(n)<=n*T(n/2)+n*T(n/2)=2*n*T(n/2)

let's consider this for only n=2^k, since T is monotonous: n=2^k and U(k)=T(2^k)

4. U(k)<=2*(2^k)*U(k-1)=2^(k+1)*U(k-1)

let L(k)=log2 U(k)

5. L(k)<=k+1+L(k-1)

just like we did between step0 and step1

6. L(k)<=k*(k-1)/2+k=k*k/2-k/2+k<=k*k

7. U(k)=2^L(k)<=2^squared(k)

8. T(n)=U(log2 n)<=2^squared(log2 n)