2
$\begingroup$

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)$?

$\endgroup$

migrated from stackoverflow.com Sep 21 '12 at 13:27

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ I've added an asnwer, but $cn\log_{10/9}(n)$ is still undecipherable. You really should put more effort in asking. For instance, what purpose serves your omission of the fact that this is about a quicksort complexity analysis? The guy in the video is not stressing the key points in his lecture so it's tough on you; just rewind and listen over again when you've missed some key point that he had mumbled over. :) $\endgroup$ – Will Ness Sep 14 '12 at 14:39
  • $\begingroup$ @Raphael thank you for editing and formatting! If it was formatted that pretty originally, I wouldn't have complained so much. :) $\endgroup$ – Will Ness Sep 21 '12 at 21:47
0
$\begingroup$
  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.

$\endgroup$
  • $\begingroup$ Great Thanks! I wasn't able to picture the whole thing that is the same as splitting an n element array. However,does Theta(n) = #leaves also hold true for other recursions like T(n) = 3*T(n/2) + n, which obviously has more than n leaves? $\endgroup$ – user1671022 Sep 14 '12 at 15:43
  • $\begingroup$ if you're processing parts of input more than once, then the total number of leaves will be more than n, I guess. $\endgroup$ – Will Ness Sep 14 '12 at 21:05
  • $\begingroup$ Wow, 2. has a weird cluster of clauses. Can you clear up the sentence(s), please? "He uses "or-equal" just because he's a mathematician who doesn't like to be wrong in some corner cases." -- well, I'd say that $<$ is wrong, then? "This is all pretty straight-forward and intuitive." -- Apparently not, at least for the OP. $\endgroup$ – Raphael Sep 21 '12 at 21:09
  • $\begingroup$ @Raphael maybe n=1 is such a corner case where < is wrong. But I don't want to think about it. I don't care to be right in the corner cases. I would be content to use "less than" and be wrong in corner cases, but I'm not a mathematician. n=1 is the case where this whole analysis is irrelevant anyway, so I don't care if my formula is right or wrong in such a case. But I'm not a mathematician. :) $\endgroup$ – Will Ness Sep 21 '12 at 21:42
  • $\begingroup$ @Raphael and thanks a lot for formatting and editing! $\endgroup$ – Will Ness Sep 21 '12 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy