+1 vote
140 views
how to compute time complexity of this kind of recurrence relation-

T(n)=T(n/2)+T(n/4)+T(n/8)+n
| 140 views
0
A much easier method in this case would be to guess it and then prove its correctness using induction.

You need to draw recursion tree to solve these type of questions.

by Active (2.2k points)
0
u didn't consider (+n) from the 1st level in the tree
0
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
why are u taking limit as infinity?
0
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
@soumya

How height is equal to (n/2^i) =1?

Thanks
0
total cost of leaf nodes has not been taken...so i think the solution won't be O(n)
0
@arvin @shaik

Please suggest how do we solve these type of problems and how do we calculate height of the recursion tree.

Thanks