The Gateway to Computer Science Excellence
+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
in Algorithms by Loyal (5.2k points) | 140 views
0
A much easier method in this case would be to guess it and then prove its correctness using induction.

1 Answer

0 votes

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

Please verify!! 

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?

Please help me in understanding

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
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
50,737 questions
57,370 answers
198,506 comments
105,272 users