Solving $T(n)=4T(n/4)+\log n$ using master theorem

Question

$T(n)=4T(n/4)+\log n$

I'm solving this recurrence relation by master theorem.

$a=4, b=4$ , $n^{\log_b a}=n^{\log_4 4}=n$

$f(n)=\log n=O(n^{1-\epsilon})$

when $\epsilon<1$, it is correct. So, $T(n)=\Theta(n)$.

But I'm confused how can $n$ be an asymptotically tight bound of $\log n$?

I'm not sure my solution is correct.

Answer 1

Let's use the other method to solve recurrences, namely, repeated substitution, assuming that $n$ is a power of 4: $$ \begin{align*} T(n) &= \log n + 4T(n/4) \\ &= \log n + 4 \log(n/4) + 16T(n/16) \\ &= \cdots \\ &= \log n + 4 \log(n/4) + 16 \log(n/16) + \cdots + (n/4) \log (n/(n/4)) + n T(1) \\ &= (n/4) \log 4 + (n/16) \log 16 + \cdots + (n/n) \log n + nT(1) \\ &= n \log 4 \left(\frac{1}{4^1} + \frac{2}{4^2} + \cdots + \frac{\log_4 n}{n}\right) + nT(1) \\ &= \frac{\log 4}{9} (4n - 3\log_4 n - 4) + nT(1) \\ &= \left(\frac{4\log 4}{9} + T(1)\right)n - \frac{\log n}{3} - \frac{4\log 4}{9}. \end{align*} $$ In particular, we see that $T(n) = \Theta(n)$.

Intuitively, what happens is that, roughly speaking, the dominant terms are $(n/4)\log(n/(n/4)) = (n/4)\log 4$ and $nT(1)$, which are both $\Theta(n)$; in the former term the logarithm is applied to a constant, and so the fact that the recurrence has $\log n$ rather than, say, $\log^2 n$ only affects the resulting hidden constant, but not the asymptotic complexity.