Solve recurrence relation for given n

Question

How do I approach the problem if I have given n. The question is to find $T(1024)$

when:

$$T(n) = 2T(n/4) + 4n + 8\text{ for }n > 1 \\ T(1) = 1 $$

Do I just substitute? In that case I get:

$2T(256)+4104$ so what do I do with $T(256)$?

Answer 1

Yes, you must substitute into the formula for $T(n)$ the value for $n$ (i.e.$1024)$.

The recurrence relation express $T(n)$ as a function of one (or more) value of $T(k)$, with $k < n$; in this case, $T(n)$ is a function of $T(n/4)$.

You must repeat the process until you reach the "base": in this case $T(1)$, and the process will certainly end after a finite number of steps.

I suppose that it is an application of the Master theorem.

We are in the Case 3 : where $f(n) = 4n+8 = \Theta (n^c)$, with $c=1$.

From : $T(n) =2T(n/4)+4n+8$, we have $a=2$ and $b=4$, so that $\log_4 2= 1/2$ and $c > 1/2$.

It follows that $T(n) = \Theta(f(n)) = \Theta(n)$.

Answer 2

$T(256)=2T(64) + 4\cdot 256 + 8$.