2
$\begingroup$

$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.

$\endgroup$
  • 1
    $\begingroup$ "how can n be an asymptotically tight bound of log n" -- who claims that? $\endgroup$ – Raphael Apr 19 '18 at 9:11
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.