# B Trees¶

## Asymptotics for tree height¶

Which statement gives you more information about a hotel?

A) The most expensive room in the hotel is $639 per night. B) Every room in the hotel is less than or equal to$639 per night.


The answer is A, since we know for sure that there is atleast one room in the hotel that costs \$639, whereas there is no guarantee of that in B. Moreover, a large number of hotels, (or motels) would fulfill the statement in B (ie, have rooms that cost a 100 bucks, but would still fulfill the statement).

In the same vein, the one of the following statements about tree height is more informative:

A) Worst case BST height is Θ(N).
B) BST height is O(N).


In this case, it's A.

Which leads to the question, why is Big O useful? It's because of the following:

• Allows us to make simple blanket statements, e.g. can just say “binary search is O(log N)” instead of “binary search is Θ(log N) in the worst case”.
• Sometimes don’t know the exact runtime, so use O to give an upper bound.