First time here? Checkout the FAQ!
0 votes
Use recursion tree method to determine Upper Bound of

T(n) = T(n-1) + T(n/2) + n
asked in Algorithms by Boss (5.3k points)   | 220 views

2 Answers

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

answered by Active (2.1k points)  
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

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)..

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

Link :

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

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 (95 points)  
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.

Related questions

0 votes
1 answer
0 votes
3 answers
+1 vote
2 answers

Top Users Sep 2017
  1. Habibkhan

    7194 Points

  2. Warrior

    2686 Points

  3. Arjun

    2594 Points

  4. rishu_darkshadow

    2568 Points

  5. A_i_$_h

    2280 Points

  6. nikunj

    1980 Points

  7. manu00x

    1856 Points

  8. makhdoom ghaya

    1770 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points

26,164 questions
33,742 answers
31,125 users