Recurrent Relation Problem

Question

I am having trouble finishing this problem for finding a recurrent relation. The problem is:

$T(n)=8T(n/2) + n^3$, $T(1)=1$ ; find $T(n)$

So I am using iteration to generate a general formula for the equation and have managed to get to the following point after performing three iterations:

$8^3T(n/2^3) + n^3 + n^3+ n^3$

I make this out to be:

$8^kT(n/2^k) + n^3(1+1+1+.... 1^k-1)$

From here I struggle and do not quite know how to proceed to find the answer. If anyone can help me it would be much appreciated.

Answer 1

Hint:

Make a change of variable:

$$n=2^m \\ T(n)=a(m)$$

This means that:

$$\frac{n}{2}=2^{m-1}$$

Then you should substitute it into the initial equation:

$$\begin{array}( T(n) & = & 8 T \left(\frac{n}{2} \right) &+&n^3 \\ \downarrow & ~ & ~\downarrow & ~ & \downarrow \\ a(m) & = & 8 a \left(m-1 \right) &+&2^{3m} \end{array}$$

Now you get a linear recurrence:

$$a(m)=8 a(m-1)+8^{m}$$

Do you know how to solve it?

Further hint:

Consider another sequence:

$$a(m)=8^{m} b(m)$$

Answer 2

When proceeding with master theorem relations $$T(bn)=a\,T(n)+f(n)$$

You can try to find a simpler relation either

• $U(n)=a\dfrac{T(n)}{n^\alpha}$
• $V(n)=a\dfrac{T(n)}{n^\alpha}+c\dfrac{f(n)}{n^\alpha}$

with a suitable choice of $\alpha$ (depends on what $f(n)$ looks like...)

See for example some instances of the second method here : solving recurrence equations and get complexity T(n)...

But sometimes it does not work and first method is preferable.

Here we have $$T(2n)=8T(n)+8n^3$$

If you try second method on this relation ( e.g. $V(n)=8\dfrac{T(n)}n+cn^2$ ), you will get nowhere, you cannot find a suitable $c$ that works.

In this case first method works fine :

Let set $U(n)=\dfrac{8T(n)}{n^3}$

Then $U(2n)=\dfrac{T(2n)}{n^3}=8\dfrac{T(n)}{n^3}+8=U(n)+8$

We have found a simpler relation $$U(2n)=U(n)+8$$

It solves to $U(2^m)=U(1)+8m$

which is equivalent to $U(n)=U(1)+8\dfrac{\ln(n)}{\ln(2)}=U(1)+8\log_2(n)$

Finally you deduce $T(n)=\dfrac{n^3U(n)}{8}=n^3(C+\log_{2}(n))$