5
$\begingroup$

I just finished reading the proof that the average height of a random binary of given size $n$ is asymptotically $2\sqrt{\pi n}$.

I'm now searching for an intuitive, or geometric, or visual proof of this asymptotic equivalence. In other words, I'm trying to find an intuitive arguments that shows that this number grows like $\sqrt{n}$.

Any ideas?
Thanks!

  • 0
    According to http://en.wikipedia.org/wiki/Random_binary_tree this is dependent on how you select a random tree. If you pick one out of all the trees of size n it does scale with $\sqrt{n}$. If you build it up in another way, it is $\log(n)$2011-01-05
  • 0
    The $lg(n)$ bound is only obtained when you build a binary search tree, not a random binary tree.2011-01-09

1 Answers 1