GATE CSE
First time here? Checkout the FAQ!
x
0 votes
246 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.9k points) 2 15 29 | 246 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 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

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 (183 points) 2 6
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
asked in Algorithms by Parshu gate Junior (627 points) 1 2 17 | 54 views
0 votes
3 answers
2
asked in Algorithms by Anmol Verma Active (1.5k points) 3 24 42 | 248 views
+2 votes
2 answers
3
asked in Algorithms by rahuldb Junior (975 points) 7 39 67 | 166 views


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23210 Points

  2. Bikram

    17018 Points

  3. Habibkhan

    6652 Points

  4. srestha

    5864 Points

  5. Debashish Deka

    5430 Points

  6. jothee

    4908 Points

  7. Sachin Mittal 1

    4762 Points

  8. joshi_nitish

    4274 Points

  9. sushmita

    3954 Points

  10. Silpa

    3698 Points


Recent Badges

Regular Juhi Sehgal
Popular Question vineet.ildm
Nice Comment Arjun
100 Club vipul verma
Notable Question jothee
Popular Question jothee
Nice Question shivangi5
Regular rinks5
Notable Question shipra tressa
Regular sasi
27,247 questions
35,056 answers
83,703 comments
33,183 users