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$ – Suresh Venkat Jan 5 '11 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$ – Suresh Venkat Jan 6 '11 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$ – Peter Shor Jan 8 '11 at 20:08

Your Answer

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

Browse other questions tagged or ask your own question.