Finding the number of leaves in a imbalanced recursion tree
Why is thetotal number of leaves in $\Theta(n)$? Because each level in recursion tree corresponds to a splitting of an array's range. When we have one element we can't split it any more so we stop. That's $\Theta(1)$ per leaf. How many 1-element areas are there in an $n$ element array? The answer is $n$.

He is summing up all levels. But levels are not all populated. Some paths down are short, some long. The more to the left in the tree, the shorter is the path. So going down the right &quot;spine&quot; of the tree, how many levels are there? $\log_{10/9}(n)$. What each level sums up to? Initially, $cn$ (where $c$ is a constant, $n$ is number of elements in the array) - while the levels are totally populated - i.e. all nodes represent splits - i.e. no one-element ranges are reached yet. Then, we start missing some leaves, so instead of &quot;equal&quot; , we can write $\leq cn$. So the total sum is less than $cn\log_{10/9}(n)$.
Or, let's go down the left spine and sum all levels up. There will be some uncounted tree to the right and down. So the total is greater than this summation, which equals $cn\log_{10}(n)$. He uses &quot;or-equal&quot; just because he's a mathematician who doesn't like to be wrong in some corner cases. :)


This is all pretty straight-forward and intuitive.