GATE CSE
First time here? Checkout the FAQ!
x
0 votes
250 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 | 250 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 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.

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 | 249 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

    23242 Points

  2. Bikram

    17048 Points

  3. Habibkhan

    7096 Points

  4. srestha

    6012 Points

  5. Debashish Deka

    5430 Points

  6. jothee

    4928 Points

  7. Sachin Mittal 1

    4762 Points

  8. joshi_nitish

    4278 Points

  9. sushmita

    3954 Points

  10. Rishi yadav

    3744 Points


Recent Badges

Popular Question Ml_Nlp
Notable Question set2018
Notable Question rahul sharma 5
Notable Question Sanjay Sharma
Notable Question Lakshman Patel RJIT
Popular Question makhdoom ghaya
Popular Question Çșȇ ʛấẗẻ
Reader kenzou
Popular Question mystylecse
Notable Question Sanjay Sharma
27,262 questions
35,076 answers
83,760 comments
33,185 users