I'm asking this silly question because I found myself trying to recall the formula for the height of a complete binary tree, to help answer the question in C++ forum about QuickSort overflowing its stack. Since it's been many years since college, all I could recall was that tree operations typically cost O(log n), and this was based on the average depth/height of a tree. So just doing a quick search without actually reading the rest of text, I found the formula the the height of a complete binary tree was log(n + 1) where n is the number of nodes.

Hitting numbers in a calculator was giving me odd results though. For example, a binary tree with height of 3, will have 2

^{3}-1 == 7 nodes. But log(7+1) == log(8) ~= 0.903. Not even close to 3. Trying ln(8) ~= 2.07, close but not yet there. It was only after I tried log

_{2}(8) did I get the correct answer.

If somebody offers a choice between algorithms that are O(log n) vs O(ln n) vs O(log

_{5}n), should I assume it is log

_{2}n, or stop and ask whether it is log

_{10}n?