Solve the recurrence relation $T(n)=3T(n/4)+n$ given that $T(1)=2$

Question

Question:

Assume that a recurrence relation is given as below:

$T(n)=3T(n/4)+n$

and we know that $T(1)=2$.

We want to solve the relation (find an explicit definition of $T(n)$ which does not rely on itself).

My solving:

Equation 1: $T(n)=3T(n/4)+n$

Equation 2: $T(n/4)=3T(n/(4^2))+n/4$

Equation 3: $T(n/(4^2))=3T(n/(4^3))+n/(4^2)$

Substituting the equations (2) and (3) in (1), we get $T(n) = (3^3)T(n/(4^3)) + ((3^2)n)/4^2 + 3n/4 + n$.

Generalizing it we get $T(n) = (3^k)T(n/(4^k)) + n[1 + 3/4 + (3/4)^2 + … + (3/4)^k-1]$

$k = \log_4(n)$

$T(n) = (3^{(\log_4(n))})*2 + 4n((3/4)^{\log_4(n)}-1)$

How to solve it further?

Answer 1

As

$$ T\left(4^{\log_4 n}\right)=3T\left(4^{\log_4 \frac n4}\right)+n $$

calling $\mathcal{T}(\cdot) = T\left(4^{(\cdot)}\right)$ and $z = \log_4 n$ we follow with the recurrence

$$ \mathcal{T}(z) = 3\mathcal{T}(z-1)+4^z $$

with solution

$$ \mathcal{T}(z) = 3^{z-1}c_0 + 4(4^z-3^z) $$

and now going backwards with $z = \log_4 n$ we arrive at

$$ T(n) = 4(n-3^{\log_4 n})+3^{\log_4 n-1}c_0 $$

and now as $T(1) = 2\Rightarrow c_0 = 6$