Solving the recurrence T(n) = T(n/2) + T(n/4) + T(n/8)?

Question

I'm trying to solve a recurrence T(n) = T(n/8) + T(n/2) + T(n/4).

I thought it would be a good idea to first try a recurrence tree method, and then use that as my guess for substitution method.

For the tree, since no work is being done at the non-leaves levels, I thought we could just ignore that, so I tried to come up with an upper bound on the # of leaves since that's the only thing that's relevant here.

I considered the height of the tree taking the longest path through T(n/2), which yields a height of log2(n). I then assume the tree is complete, with all levels filled (ie. we have 3T(n/2)), and so we would have 3^i nodes at each level, and so n^(log2(3)) leaves. T(n) would then be O(n^log2(3)).

Unfortunately I think this is an unreasonable upper bound, I think I've made it a bit too high... Any advice on how to tackle this?

Answer 1

One trick you can use here is rewriting the recurrence in terms of another variable. Let's suppose that you write n = 2^k. Then the recurrence simplifies to

T(2^k) = T(2^k-3) + T(2^k-2) + T(2^k-1).

Let's let S(k) = T(2^k). This means that you can rewrite this recurrence as

S(k) = S(k-3) + S(k-2) + S(k-1).

Let's assume the base cases are S(0) = S(1) = S(2) = 1, just for simplicity. Given this, you can then use a variety of approaches to solve this recurrence. For example, the annihilator method (section 5 of the link) would be great here for solving this recurrence, since it's a linear recurrence. If you use the annihilator approach here, you get that

S(k) - S(k - 1) - S(k - 2) - S(k - 3) = 0

S(k+3) - S(k+2) - S(k+1) - S(k) = 0

(E³ - E² - E - 1)S(k) = 0

If you find the roots of the equation E³ - E² - E - 1, then you can write the solution to the recurrence as a linear combination of those roots raised to the power of k. In this case, it turns out that the recurrence is similar to that for the Tribonacci numbers, and if you solve everything you'll find that the recurrence solves to something of the form O(1.83929^k).

Now, since you know that 2^k = n, we know that k = lg n. Therefore, the recurrence solves to O(1.83929^{lg n}). Let's let a = 1.83929. Then the solution has the form O(a^{lg n}) = O(a^{(log_a n) / log_a2)}) = O(n^{1/log_a 2}). This works out to approximately O(n^0.87914...). Your initial upper bound of O(n^{lg 3}) = O(n^{1.584962501...}) is significantly weaker than this one.

Hope this helps!