I'm wondering where (how? why?) my reasoning (by imagining the recursion tree) deviates from the application of the Master Theorem (Case 1) to this recurrence.

The Master Theorem gives $\Theta(n^{\log_{5}4})$, whereas reasoning from the recursion tree gives me $\Omega({\log n})$ and $O(\log^{2}n)$.

My rationale:

  • Each level of the recursion tree totals $4^{L}\left(\log\frac{n}{5^{L}}\right)$ work, where $L$ is the level of the tree (zero-indexed). There are roughly $\lceil\log_{5}n\rceil$ levels in total, so roughly, this much work is being done:

$$ \begin{align*} \sum_{L=0}^{\lceil\log_{5}n\rceil} 4^{L} \log \frac{n}{5^{L}} &\leq (1 + \log_{5} n) (\log n)\\ &= O(\log^{2} n) \end{align*} $$

  • A lower bound can be found by just taking the work done at the root of the tree: $\Omega(\log n)$.

I think I'm incorrectly assuming the work done at the root ($\log n$) serves as a per-level upper-bound. (I figured this was the case since at the leaf-level ($L = \log_{5} n$), the amount of work is $4^{\log_{5}n} (\log 1) = 0$?) I do notice that $4^{\log_{5}n} = n^{\log_{5}4}$, which is what the Master Theorem produces, but I can't square this with the tree.

  • $\begingroup$ how do you get the inequality? $4^L \log \frac{n}{5^L} = \log (\frac{n}{5^L})^{4^L}$. It seems strange to upperbound that with simple $\log n$ $\endgroup$ Commented Feb 2 at 5:01
  • $\begingroup$ if you lower $+\log n$ term to a simple $+1$, does you argument still work? $\endgroup$ Commented Feb 2 at 5:04
  • $\begingroup$ @NooneAtAll3, yep, you're right -- I mistakenly upperbounded the level-by-level work with that (incorrectly thinking the root did at least much work as any subsequent level). $\endgroup$
    – Per48edjes
    Commented Feb 3 at 2:14


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.