TITLE: Solving a recurrence relation $T(n) = 2T(\frac{n}{4}) + c$
QUESTION [1 upvotes]: 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}$$

REPLY [0 votes]: 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).$$
{"set_name": "stack_exchange", "score": 1, "question_id": 316646}