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
  • 1
    $\begingroup$ "how can n be an asymptotically tight bound of log n" -- who claims that? $\endgroup$
    – Raphael
    Apr 19, 2018 at 9:11

1 Answer 1

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 and acknowledge you have read our privacy policy.

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