How to solve: T(n) = T(n/2) + T(n/4) + T(n/8) + (n)

Question

I know how to do recurrence relations for algorithms that only call itself once, but I'm not sure how to do something that calls itself multiple times in one occurrence.

For example:

T(n) = T(n/2) + T(n/4) + T(n/8) + (n)

Answer 1

Use Recursion Tree. See the last example of Recursion tree at CLRS "Intro to Algorithm".

T(n) = T(n/2) + T(n/4) + T(n/8) + n. The root will be n(cost) & divided into 3 recursions. So the recursion tree looks like as follows:

T(n) = n = n T(n/2)T(n/4)T(n/8) (n/2) (n/4) (n/8) T(n/4)T(n/8)T(n/16) T(n/8)T(n/16)T(n/32) T(n/16)T(n/32)T(n/64)

                                             n---------------------------------> n      

                             (n/2)         (n/4)           (n/8)--------------> (7/8)n

                         n/4 n/8 n/16  n/8 n/16 n/32  n/16 n/32 n/64)--------> (49/64)n
                                            ...         

Longest path: the leftmost left branch = n -> n/2 -> n/4 -> ... -> 1

Shortest branch: the rightmost right branch = n -> n/8 -> n->64 -> ... -> 1

The number of leaves (l): 3^log_8(n) < l < 3^log_2(n) => n^0.5 < l < n^1.585

Look at the tree - upto log_8(n) levels the tree is full, and then as we go down, more & more internal nodes are absent. By this theory we can give the bound,

T(n) = Big-Oh (Summation j=0 to log_2(n)-1 (7/8)^j n) = ... => T(n) = O(n). T(n) = Big-Omega (Summation j=0 to log_8(n)-1 (7/8)^j n) = ... => T(n) = Big-Omega(n).

Therefore, T(n) = Theta(n).

Here the points are: T(n/2) path has the highest length...

This must not be a complete ternary tree ... height = log base 2 of n & # of leaves must be less than n ...

Hope, likely this way u can solve the prob.