Comment on page

# 17.2 Big O vs. Worst Case

A short digression on asymptotics
Consider the following statements about BSTs. Which of the following are true?
1. 1.
The worst-case height of a BST is
$\Theta(N)$
.
2. 2.
BST height is
$O(N)$
.
3. 3.
BST height is
$O(N^2)$
.
The answer is that all three statements are true. BSTs always have a height that is linear or better, and a linear height is obviously "less than" the quadratic upper bound in the last point.
However, a more tricky question is which of the three statements is the most informative.
The answer here is the first statement: it gives an exact upper and lower bound unlike the other statements.
$O(N)$
could mean linear, logarithmic, square-root, or constant, but
$\Theta(N)$
can only mean linear.
For an analogy, consider the following statements about the worst-case cost of a hotel room:
1. 1.
The most expensive room is $639/night. 2. 2. The most expensive room is less than or equal to$2000/night.
Here, we see that the first statement gives us exact information, whereas the second statement does not. In the second statement, the most expensive room could be $2000,$10, or anywhere in between.
However, both are statements about the worst case. Applying this to asymptotic notation, this means that we can refer to the worst case with
$\Theta$
,
$O$
, or even
$\Omega$
. Big O is not the same as the worst case!

## Using Big O

If
$\Theta$
$O$
$O(\log N)$
$\Theta(log N)$