GATE CSE
First time here? Checkout the FAQ!
x
0 votes
220 views
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
O(n2^n)??

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.

so,t(n)=1+2+3+4+5+....+n=O(n^2)
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

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

Link : https://drive.google.com/file/d/0B2zVzfkXsyqfYl9hODBXdklxcFE/view

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
1
0 votes
3 answers
2
+1 vote
2 answers
3


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
79,996 comments
31,125 users