> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook-spring-2026/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b-2.gitbook.io/cs61b-textbook-spring-2026/15.-bsts/15.6-big-o-vs.-worst-case.md).

# 15.6 Big O vs. Worst Case

Consider the following statements about BSTs. Which of the following are true?

1. The worst-case height of a BST is $$\Theta(N)$$.
2. BST height is $$O(N)$$.
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. Theta is always a more informative statement than big O.

Think about theta as similar to $$=$$. When we say some function $$F(N) \in theta(N)$$ we mean it grows exactly linearly.

By contrast, you should think of $$O$$ as $$<=$$. If we say some function $$f(N) \in O(N)$$, the we mean it grows at a linear rate or slower.

As a specific example, suppose we know that $$f(N)$$ is one of these functions: $$3N$$, $$4log N + 6$$. If I tell you that $$f(N) \in O(N)$$ you have no idea which function we're talking about. But if I say $$f(N) \in theta(N)$$, you know immediately which one we mean.

For an analogy, consider the following statements about the worst-case cost of a hotel room:

1. The most expensive room is $639/night.
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$$ is always more informative than $$O$$, then why do we bother using Big O notation at all? There are several reasons:

* We can make broader statements. For example, saying "binary search is $$O(\log N)$$ is correct, but saying "binary search tree is $$\Theta(log N)$$" would not be correct, since it can be constant in certain scenarios.
* Sometimes, it is not possible or extremely difficult to determine the exact runtime. In such cases, we would still like to provide a generalized upper bound.


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://cs61b-2.gitbook.io/cs61b-textbook-spring-2026/15.-bsts/15.6-big-o-vs.-worst-case.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.