2
$\begingroup$

I am trying to develop the intuition of the master theorem for the case where $a > b^{d}$ [Case 3] in this video. In the video, they say that since most of the work is done at the leaves, we should expect $O(\text{number of leaves})$ but I don't see how that is similar to $O(n^{\log_b a}$), which one would get from the proof.

I just need the connection to the intuition as in how to see $O(n^{\log_b a}$) from $O(\text{number of leaves})$ even in the least rigorous way. I don't need the actual proof. The presenter gets on to the proof where $n$ is a power of $b$ later on, which is easier to follow but I would like to know so that I don't have to look up the material every time I need to check my work. Given the order of the presentation, I suspect that the intuition can be obtained without the proof for now but I could also be wrong and would appreciate being corrected if that's the case.

$\endgroup$
2
$\begingroup$

The recurrence in question is $T(n) = aT(n/b) + f(n)$. Suppose that $n = b^k$, and the leaves are at $n = 1$. The root $b^k$ has $a$ children labelled $b^{k-1}$ (the label is the size of the subproblem). Each one of them has $a$ children labelled $b^{k-2}$, and in total there are $a^2$ children at depth $2$ labelled $b^{k-2}$. More generally, there are $a^\ell$ children at depth $\ell$ labelled $b^{k-\ell}$. In particular, taking $k = \ell$, we see that there are $a^k$ leaves. Since $n = b^k$, we get that the number of leaves is $$ a^k = (b^{\log_b a})^k = (b^k)^{\log_b a} = n^{\log_b a}. $$

$\endgroup$
10
  • $\begingroup$ What do you mean by labelled? Is it the size of the subproblem as that is what I can link to? $\endgroup$ – heretoinfinity Jan 2 at 22:01
  • $\begingroup$ Right, it's the size of the subproblem. $\endgroup$ – Yuval Filmus Jan 2 at 22:03
  • $\begingroup$ How did you get from $a^k$ to $(b^{\log_b a})^k$ in the last line? $\endgroup$ – heretoinfinity Jan 2 at 22:11
  • $\begingroup$ What is the definition of $\log_b a$? $\endgroup$ – Yuval Filmus Jan 2 at 22:13
  • 1
    $\begingroup$ @heretoinfinity - The maximum number of levels is $\log_b n$. $\endgroup$ – HEKTO Jan 3 at 4:25

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.