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)

Echolalia

should go to the cstheory one - how do you recommend a question for migration anyway? – Gascon

What do you mean by "do recurrence relations"? – Aggress

@Gascon - you would flag it, but I doubt this is a research-level comp sci question – Aggress

@Robin Something like this – Echolalia

This is not a CS theory question but simple problem in practical complexity analysis – Dillion

The incorrect answer below illustrates why you should never just say "do recurrence relations" in a question. It's far too ambiguous! – Aggress

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.

Benefic

Answer 2

See the Image for a better explanation-

Height of Tree: We took log(n)(base 2) because n/2 make the tree longer in comparison to n/4, and n/8. And our GP series will go till k=logn(base).

Papistry

why n/2^k = 1 ? – Millburn

Because at some point of time, a particular value of k will lead this expression to 1. This is assumed like this to get value of k and value of k will let us know that what is the tree height. – Papistry

Answer 3

There are two ways of solving this. One is unrolling recursion and finding similarities which can require inventiveness and can be really hard. Another way is to use Akra-Bazzi method.

In this case g(x) = n, a1 = a2 = a3 = 1 and b1 = 1/2, b2 = 1/4, b3 = 1/8. Solving the equation

which is 1/2^p + 1/4^p + 1/8^p = 1 you get p = 0.87915. Solving the integral you will get , which means that the complexity is: O(n)

Johst

Answer 4

Just like coding the Fibonacci Sequence (the hard way) as an example, you would simply type something along the lines of:

long fib(long n){
 if(n <= 1) return n; 
 else return fib(n-1) + fib(n-2);
}     

Or, better yet, memoize it using a global variable to make it much quicker. Once again, with the Fibonacci Sequence:

static ArrayList<Long>fib_global = new ArrayList(1000); 
  //delcare a global variable that can be appended to
long fib(long n){
   if(n >= fib_global.length)fib_global.add(fib(n-1) + fib(n-2));
   return fib_global.get(n);
}

The code will only execute one of these calls at a time, and most likely in the left-to-right order you typed them in, making it so that you only don't really need to worry about the amount of times you needed to call something.

Snuffbox

Answer 5

As CLRS has said, T(n) can be replaced by cn by mathematical induction. This inductive assumption works for the number below n. As mentioned above, what we need to prove is that the parameter value is n. Therefore, as follows: assume: T(n) <= cn for the number below n; conclude:

T(n) = T(n/2) + T(n/4) + T(n/8) + n
    <= c/2*n + c/4*n + c/8*n + n
     = (7/8*c + 1) * n
    <= cn (when c >= 8)

that's all.

Briefs