Time Complexity

0 votes

What is the worst case time complexity of the following recurrence relation?
T(n)=T(n/2)+T(n/4)+T(n/8)+n

My question is if we use Recursion tree method then we get tree something like this

the work done at every level is in the form of GP So we can write  T(n) = n+(7/8)n +(7/8)n^2 ....... which will come out as theta(n)   

Theta(n) would be the answer or we will have to multiply it with the height (LOG(n) base 2) of the tree (leftmost height as it will ne the first to terminate)???????

asked Dec 30, 2016 in Data Structures Algorithms and C Programming by hi2saifgmail-com (2,280 points)

Please log in or register to answer this question.

...