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?

Note: This is a duplicate of https://math.stackexchange.com/questions/16457 , but I couldn't find how to move it to this website. Sorry!

  • 1
    $\begingroup$ you can ask a moderator on math.SE to migrate it over here. I can't do it, because a mod on the originating site needs to do it. If you want to, best to flag it for mod attention and ask them to do it. $\endgroup$ Jan 5, 2011 at 19:35
  • 2
    $\begingroup$ I should note that this question already has some good answers on math.SE, raising the question of whether it needs to continue here. $\endgroup$ Jan 6, 2011 at 18:22
  • $\begingroup$ Is this a random labeled or unlabeled binary tree (I expect for the $\sqrt{n}$ bound it doesn't matter). $\endgroup$ Jan 8, 2011 at 20:08


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.