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 Show 8 previous comments 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.