Height of a Balanced Binary Search tree

Question

Why is the maximum time to reach an element in a Balanced Binary Search tree is log n, when in reality, a perfectly balanced tree has 1, 3, 7, 15 elements (that is 1 less than a multiple of 2). The answer given here Why is the height of a balanced binary search tree log(n)? (Proof) is saying let's assume we have 2^N nodes (a multiple of 2)

But, if we take a log of those odd numbers, we won't get a round number for height!

Question:

Is it really log(n+1) but then we discard +1 since it's negligible at huge n?

Answer 1

Constants are removed from O(..) notation unless they matter. In your example adding + 1 doesn't affect the runtime so we'd talk about O(log n) instead of O(log n + 1).

In any case, looking up an element in a balanced binary tree is O(log n) because at each step you're halving the size of tree that you still need to search through. This big O notation expresses the runtime of the algorithm as n grows, it's not intended as way of computing the number of operations that you'll do (as there may be some additional operations involved etc).

Note that the question you linked to talks about 2 ^ N leaf nodes so a balanced binary tree with 2 ^ 2 = 4 leaf nodes would have 7 total nodes. The meaning of N in that other question isn't the same as n in this question.

Answer 2

It's the lowest upper bound, meaning it is reached for some n. Note that the trivial tree with the root only has a height defined to be 0, not 1 as you probably assumed. E.g. a perfectly balanced tree with 3 elements has height 1 and a tree with 4 elements has height 2 which is log(4).