250 views
Use recursion tree method to determine Upper Bound of

T(n) = T(n-1) + T(n/2) + n
O(n2^n)??

It should be n^2.

Because t(n/2) part only goes till logn depth but t(n-1) part goes till ndepth and cost of each stage is equal to size of problem at that level.

so,t(n)=1+2+3+4+5+....+n=O(n^2)
answered by Loyal (2.5k points) 2 8 25
it's O(n^2)

please correct me if i'am wrong.
@jatin and @sachi
Would you please draw the recursion tree so that it will be easy to understand.?

In worst case n-1 levels with each level cost n so total cost = n *n= O(n2)

I think cost of each level is not n.
it is n , 3/2n , 9/4n  up to n terms (GP Series)
cost at each level O(n). :) Since upper bound is ask.
I thought , you took appropriate value.
Thanks Prashant.

Can we do this way:

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

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

meaning for one line we need T(n/2)+n time.

Using Master's theorem we got one Theta(n). So for n lines it will be n*Theta(n) = Theta(n2)

and sum of this gp for n terms will tend to n(1.5)^n..?? so why complexity is not O(n2^n)..

@Joshi
I am also getting same answer that the complexity is O(n*(3/2)n)

we can say O(n*2n)
If you check the link, the approach is totally difference. But I do not know whether it is correct or not

the solution given in link is no doubt provide more tight upper bound than we have found(n2^n)....the solution is taking T(n/2)=T((n+1)/2)....but we have taken T(n/2)!=T((n+1)/2) with (T(n+1/2) > T(n/2))...this will make very large difference as the term are decreasing exponentially..

I used Back substitution method for solving this particular problem. you can see the attached image.

The answer according to my approach is O(n^2).

EDIT- in the below image,read f(n) = n(n+1)/2  (in last third line)

answered by (183 points) 2 7
You are doing it wrong -- in each expansion of T (n), T(n/2) term will be there.
sir the cost at each level is going like n , 3n/2, 9n/4, 27n/8.......upto n terms, it is a geometric series and sum is around  n(1.5)^n which is equal to O(n2^n)

please correct me if i am wrong
Yes Sir,
I am also thinking that it is not a correct approach that Sachi has followed.
@Sachi  thanks for the approach.
can anyone give the correct approach for this question.