Timeline for Proof that a randomly built binary search tree has logarithmic height
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 30, 2016 at 0:22 | comment | added | Merbs | @DavidNathan I don't understand your concern - are you doubting that 1/n is a constant or that it can be moved outside the summation? It, like the constant 2, is largely taken out for illustrative purposes, to simplify the remaining proof. | |
| Dec 31, 2013 at 0:06 | comment | added | Merbs |
@Zeks So, we can choose other binomials with larger terms. If the term is still polynomial (n^k), the conclusion is the same because the k is dropped in the big-O notation (the way 3 was dropped). But if we substituted in something exponential (e^n), it would still be a correct upper bound, just not a tight one. We know that the expected height is at least logarithmic, so determining that it is at most logarithmic makes it tight.
|
|
| Dec 29, 2013 at 16:21 | comment | added | Zeks | but why exactly is exponential height less than or equal the chosen binomial? I still don't understand why can't we choose any other binomial with different largest term and do exactly the same math... probably I'm stupid but I just can't see why ... and up to this point proof makes perfect sense, then they just had to pull something completely out of the blue and with no explanation tell us it "proves" them being right... | |
| Nov 25, 2012 at 18:57 | vote | accept | user1675999 | ||
| Oct 29, 2012 at 0:12 | comment | added | user1675999 | WOW.THANKS !!!! Even though i don't know about Expected value, this sort of makes sense. I did not do a discreet math course before doing algorithms. I will post more comments, if i have some doubt. Thank you Merbs. | |
| Oct 28, 2012 at 12:56 | history | edited | Merbs | CC BY-SA 3.0 |
Improved formatting slightly for previous edit; added some additional commentary/speculation
|
| Oct 28, 2012 at 12:37 | history | answered | Merbs | CC BY-SA 3.0 |