1 votes 1 votes how to compute time complexity of this kind of recurrence relation- T(n)=T(n/2)+T(n/4)+T(n/8)+n Algorithms time-complexity algorithms asymptotic-notation recurrence-relation + – aditi19 asked Oct 27, 2018 aditi19 832 views answer comment Share Follow See 1 comment See all 1 1 comment reply goxul commented Oct 31, 2018 reply Follow Share A much easier method in this case would be to guess it and then prove its correctness using induction. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes You need to draw recursion tree to solve these type of questions. Please verify!! Soumya Tiwari answered Oct 27, 2018 Soumya Tiwari comment Share Follow See all 7 Comments See all 7 7 Comments reply aditi19 commented Oct 27, 2018 reply Follow Share u didn't consider (+n) from the 1st level in the tree 0 votes 0 votes Soumya Tiwari commented Oct 27, 2018 reply Follow Share The term n in recurrence relation represent the cost at the top level of recursion and the rest 3 term represent the cost incurred by subproblem of size n/2,n/4,n/8 0 votes 0 votes aditi19 commented Oct 27, 2018 reply Follow Share why are u taking limit as infinity? 0 votes 0 votes Soumya Tiwari commented Oct 28, 2018 reply Follow Share Try solving the equation 1 by yourself as you will see it'll add only a constant factor which will be ignored while taking asymtotic notation. Also as the common factor is 7/8 which is <1 thus we can take n->infinity 0 votes 0 votes Mayankprakash commented Nov 17, 2018 reply Follow Share @soumya How height is equal to (n/2^i) =1? Please help me in understanding Thanks 0 votes 0 votes Navneet Kalra commented Jan 4, 2019 reply Follow Share total cost of leaf nodes has not been taken...so i think the solution won't be O(n) 0 votes 0 votes Mayankprakash commented Jan 4, 2019 reply Follow Share @arvin @shaik Please suggest how do we solve these type of problems and how do we calculate height of the recursion tree. Thanks 0 votes 0 votes Please log in or register to add a comment.