# Solving a recurrence relation

I have a recurrence relation that I would like to solve. $T(n)$ belongs to $\Theta(f(n))$.

$T(n) = 2T(\frac{n}{4}) + c$, where $c$ is a constant. The base case, $T(1)$ is a constant as well.

My approach was to let $n = 4^k$, but I guess I got confused with the expansion. Can someone show me the first couple of expansions and the closed form? Would appreciate it as it would help me learn this.

EDIT: My work so far ... \begin{align} T(4^k) &= 2&T(4^k) & &+ c \\ &= 2&(2T(4^{k-1}) &+ c) &+c \\ &= 2&(2T(2T(4^{k-2}) + c) &+ c) &+c \end{align}

-

Let $x_k = T(4^k)$. Then $x_{k+1} = 2 x_k +c$. The solution is $x_k = 2^k x_o + c (2^k-1)$. Hence $T(4^k) = 2^kT(1)+c(2^k-1)$.

Letting $n = 4^k$ gives $2^k = \sqrt{n}$, so we have $T(n) = \sqrt{n}T(1) + c(\sqrt{n}-1)$ (for $n \in \{ 4^k \}_{k \in \mathbb{N}}$).

-
thank you for your response. Did you get your answer by plugging it into the recurrence relation? Did it look like something like this? let n=^k, T(4^k)= 2T(4^k) + c ... 2[2T[4^(k-1)] + c] +c ... 2[2T[2T[4^(k-2)] + c] + c] +c – Masterminder Feb 28 '13 at 7:43
No. I transformed it into the linear system $x_{k+1} = 2 x_k +c$ which has a standard solution. $x_{k+1} = T(4^{k+1}) = 2T(4^k) +c = 2 x_k +c$. – copper.hat Feb 28 '13 at 7:45
Do you mind looking at my steps in top and tell me if I am correctly recursing on it? I am not sure if I should be dividing c by 4. – Masterminder Feb 28 '13 at 7:52
I want to see if I can get what you got – Masterminder Feb 28 '13 at 7:55
Just apply the formula. $T(4^k) = 2 T(4^{k-1})+c = 2 (2 T(4^{k-2})+c)+c = 2^2 T(4^{k-2}) + c(2^1+2^0)$. – copper.hat Feb 28 '13 at 8:37

This is a very simple case of the Master theorem that can be solved exactly, the way that was done here. Let the representation in base 4 of $n$ be given by $$n = \sum_{k=0}^{\lfloor \log_4 n \rfloor} d_k 4^k.$$

Now with $T(0)=0$, we have $$T(n) = \sum_{j=0}^{\lfloor \log_4 n \rfloor} (2^j \times c) = c \left(2^{\lfloor \log_4 n \rfloor+1} -1\right).$$

Observe that $$\log_4 n - 1 < \lfloor \log_4 n \rfloor \le \log_4 n$$ so that $$2^{\log_4 n} < 2^{\lfloor \log_4 n \rfloor+1} \le 2n^{\log_4 n} \quad \text{and} \quad c(\sqrt n-1) < T(n) \le c(2\sqrt n-1).$$ This allows us to conclude that $$T(n) \in \Theta(\sqrt n).$$

-