Where does this recursion formula come from?

Question

I come across an explanation of recursion complexity. This screenshot is in question:

How do you get this?

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

The $log_n^4$ shown seems to be base 4, and this baffles me. What does the n superscript stand for? I am inclined to think the base of this log should be 3. Can someone explain this to me?

---

Another example was provided where the tree expands at an exponent of 2:

The formula given is:

T(n) = 2T(n/2) + 2

The log(n) given is said to be of base 2. This makes sense to me, but not the base 4 in given by the first picture.

Answer 1

In this example, we're considering an algorithm that, given a problem of size $n$, does 1 unit of "local" work and divides the remaining work into 3 smaller problems of the same kind, where each of these subproblems has size $n/4$. (Instead of 3 and 4 we could have any numbers; this is just an example.) So if $T(n)$ is the total amount of work done in solving a problem of size $n$, we have the equation $T(n)=3T(n/4)+1$ by assumption.

The tree figure shows a way of thinking about the algorithm and understanding the growth rate of $T$. At $k$ levels below the root, we have $3^k$ subproblems and each subproblem has size $n/4^k$. Since our algorithm stops splitting the problem up when it reaches a base case (i.e. a problem of size 1), the tree has $\log_4n$ levels, and the number of base cases at the bottom level is $3^{\log_4n}$.

Answer 2

$\begin{array}\\ T(n) &=3T(n/4)+1\\ &=3(3T(n/16)+1)+1\\ &=9T(n/16)+4\\ &=9(3T(n/64)+1)+4\\ &=27T(n/64)+13\\ &.....\\ &=3^kT(n/4^k)+\sum_{j=0}^{k-1}3^j \qquad\text{conjecture}\\ &=3^k(3T(n/4^{k+1})+1)+\sum_{j=0}^{k-1}3^j \qquad\text{induction step}\\ &=3^{k+1}T(n/4^{k+1})+3^k+\sum_{j=0}^{k-1}3^j\\ &=3^{k+1}T(n/4^{k+1})+\sum_{j=0}^{k}3^j \qquad\text{confirmed}\\ \end{array} $

Note that the induction stops when $4^k \ge n$.

Also note that $\sum_{j=0}^{k-1}3^j =\dfrac{3^k-1}{3-1} =\dfrac{3^k-1}{2} $.