# Intuition on O(number of leaves) for master theorem

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.

## 1 Answer

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

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