in Algorithms
735 views
3 votes
3 votes
$$T(n)\quad=\quad T(n-1)+T \left (\frac{n}{2} \right )+n$$ $$n \geq 1, \quad T(1)=1$$
in Algorithms
by
735 views

3 Answers

1 vote
1 vote

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(2n)

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

1 comment

For GATE this should be sufficient I guess. It is hard to do better.
0
0
0 votes
0 votes
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

1 comment

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.
0
0
0 votes
0 votes
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

3 Comments

That result is easy to get- but that's not the actual result rt?
0
0
I can't undersrand . may u help me understand it . arjun .
0
0
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.
0
0

Related questions