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 &gt; 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.
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}.
$$