Jtdylktuy

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.

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)$$

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

You can try to find a simpler relation either

• 
  $U(n)=adfrac{T(n)}{n^alpha}$


• 
  $V(n)=adfrac{T(n)}{n^alpha}+cdfrac{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)=8dfrac{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}=8dfrac{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)+8dfrac{ln(n)}{ln(2)}=U(1)+8log_2(n)$

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