How can one solve the following recurrence?

Question

$$T(n)\quad=\quad T(n-1)+T \left (\frac{n}{2} \right )+n$$ $$n \geq 1, \quad T(1)=1$$

Answer 1

I dont know the exact answer but this is my approach.

let the             T(n-1)=T(n/2)                                     T(n/2)=T(n-1)

T(n)=                 2T(n/2)+n    < T(n)=T(n−1)+T(n/2)+n   <  T(n)=2T(n−1)+n

                       Ώ(nlogn)       <           T(n)                   <       O(2ⁿ)

so i guess answer should in exponential term for big-Oh.

Comments

For GATE this should be sufficient I guess. It is hard to do better.

Answer 2

I'm not sure. I'm trying to get it right.

T(n) = T(n-1)+T(n/2)+n

As we know we Asymptotic notation by equalities and inequalities, we can represent a part of Sub expression in RHS with a Approx Fn.

lets consider T(n/2)+n. By applying masters theorem we get => O(n).

So Our initial Eqn becomes, T(n)= T(n-1)+O(n).  Now if we apply masters theorem we get T(n)= O(n^2).

 

Please Correct me if im wrong

Comments

Nopes. I don't think you can do that. Because T(n/2) in turn has a term for T(n/2 - 1). So, there is no easy way here.

Answer 3

i can't understand the solution although here. but no specific complexity of the question http://clrs.skanev.com/04/04/05.html its corman solution ite it will be very handy if u r solving coreman http://clrs.skanev.com/04/04/05.html

Comments

That result is easy to get- but that's not the actual result rt?

---

I can't undersrand . may u help me understand it . arjun .

---

We can replace $n/2$ with $n-1$ in the recursion and solve and get $O\left(2^n\right)$. Also, we can replace $n-1$ with $n/2$ and get $\Omega \left(n \lg n\right)$ as lower bound. To make the bounds tight is out of GATE scope I believe.