0 votes 0 votes Use recursion tree method to determine Upper Bound of T(n) = T(n-1) + T(n/2) + n Algorithms algorithms time-complexity + – Arnab Bhadra asked Jun 30, 2017 Arnab Bhadra 2.0k views answer comment Share Follow See 1 comment See all 1 1 comment reply joshi_nitish commented Jun 30, 2017 reply Follow Share O(n2^n)?? 0 votes 0 votes Please log in or register to add a comment.
0 votes 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) jatin saini answered Jul 1, 2017 jatin saini comment Share Follow See all 11 Comments See all 11 11 Comments reply Sachi Saxena commented Jul 1, 2017 reply Follow Share it's O(n^2) please correct me if i'am wrong. 0 votes 0 votes Arnab Bhadra commented Jul 1, 2017 reply Follow Share @jatin and @sachi Would you please draw the recursion tree so that it will be easy to understand.? 0 votes 0 votes Prashant. commented Jul 2, 2017 reply Follow Share In worst case n-1 levels with each level cost n so total cost = n *n= O(n2) 1 votes 1 votes Arnab Bhadra commented Jul 2, 2017 i reshown by Arnab Bhadra Jul 2, 2017 reply Follow Share I think cost of each level is not n. it is n , 3/2n , 9/4n up to n terms (GP Series) 0 votes 0 votes Prashant. commented Jul 2, 2017 reply Follow Share cost at each level O(n). :) Since upper bound is ask. 0 votes 0 votes Arnab Bhadra commented Jul 2, 2017 reply Follow Share I thought , you took appropriate value. Thanks Prashant. 1 votes 1 votes Saikat commented Jul 3, 2017 reply Follow Share 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) 0 votes 0 votes Arnab Bhadra commented Jul 3, 2017 reply Follow Share @Saikat Check the link https://drive.google.com/file/d/0B2zVzfkXsyqfYl9hODBXdklxcFE/view 0 votes 0 votes joshi_nitish commented Jul 3, 2017 reply Follow Share and sum of this gp for n terms will tend to n(1.5)^n..?? so why complexity is not O(n2^n).. 0 votes 0 votes Arnab Bhadra commented Jul 3, 2017 reply Follow Share @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 0 votes 0 votes joshi_nitish commented Jul 3, 2017 reply Follow Share 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 0 votes Please log in or register to add a comment.
0 votes 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) Sachi Saxena answered Jul 2, 2017 Sachi Saxena comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Arnab Bhadra commented Jul 2, 2017 reply Follow Share Yes Sir, I am also thinking that it is not a correct approach that Sachi has followed. @Sachi thanks for the approach. 0 votes 0 votes Sachi Saxena commented Jul 2, 2017 reply Follow Share can anyone give the correct approach for this question. 0 votes 0 votes Arnab Bhadra commented Jul 2, 2017 reply Follow Share @Sachi Check the link https://drive.google.com/file/d/0B2zVzfkXsyqfYl9hODBXdklxcFE/view 0 votes 0 votes Please log in or register to add a comment.