Finding the number of leaves in a imbalanced recursion tree

Question

I'm going through the MIT Online Course Videos on Intro. to Algorithms at here at around 38:00.

So we have a recursion formula

$\qquad T(n) = T(n/10) + T(9n/10) + O(n)$

If we build a recursion tree it looks like

                   T(n)                     -- Level 1       = c*n
             /               \
       T(n/10)             T(9n/10)         -- Level 2       = c*n
        /   \             /         \
 T(n/100)  T(9n/100) T(9n/100)  T(81n/100)  -- Level 3       = c*n

   /                                  \                      <= c*n
    .                                .
    .                                .
 0(1)                                 0(1)

where $c$ is a constant larger than $0$.

Shortest path from the root to the leaf is $\log_{10}(n)$.

Longest path from the root to the leaf is $\log_{10/9}(n)$

Therefore, the cost could be calculated as Cost = Cost of each level * number of levels.

With the shortest path cost, we get a lower bound of $cn\log_{10}(n)$, and with the longest path cost an upper bound of $cn\log_{10/9}(n)$.

And now I have to add the costs of leaf nodes, which leads to my problem. In the video it says the total number of leaves is in $\Theta(n)$. I have trouble figuring out how he got to $\Theta(n)$.

The video further says $T(n)$ is bounded by

$\qquad cn\log_{10}(n) + O(n) \leq T(n) \leq cn\log_{10/9}(n) + O(n)$

Wouldn't it make more sense to say it's

$\qquad cn\log_{10}(n) + O(n^{\log_{10}(2)}) \leq T(n) \leq cn\log_{10/9}(n) + O(n^{\log_{10/9}(2)})$

where $\Theta(n^{log_{10}(2)})$ represents the leaves on the left and $\Theta(n^{\log_{10/9}(2)})$ represents the leaves on the right.

Or is there a way to simplify these terms to $\Theta(n)$?

Answer 1

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

2. 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 "spine" 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 "equal" , 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 "or-equal" 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.