Does Big O measure the worst-case scenario or the average case?

By definition, Big O represents the mathematical upper bound, meaning it describes the worst-case scenario. However, in industry, people sometimes use it loosely to describe the average case. Strictly speaking, you can calculate the Big O of the best, worst, or average case, but we usually care most about the worst case so our program doesn't freeze.

Is a lower Big O always faster?

Not necessarily for small inputs. An algorithm that is $O(n)$ might take $1000n$ steps, while an $O(n^2)$ algorithm might take just $1n^2$ steps. If $n = 5$, the $O(n^2)$ algorithm takes 25 steps, while the $O(n)$ takes 5000 steps. But as $n$ approaches infinity, the lower Big O will always eventually win.

$O(1)$ means constant time. It means the runtime does not change at all regardless of how big the input gets. Checking if a number is even or odd is $O(1)$ whether the number is 4 or 4,000,000.

What does Big O notation actually measure?

Big O notation measures the growth rate of an algorithm's resource usage (usually time or memory) relative to the size of its input. Instead of telling you exactly how many seconds a program will take to run, it tells you how much longer it will take if you double, triple, or massively increase the amount of data it has to process.

Think of it like buying groceries. If you buy a single item, it takes a certain amount of time. If you buy ten times as many items, does your shopping time stay the same, increase by ten times, or take a hundred times longer because you have to mathematically compare every item to every other item in your cart? Big O gives us a standardized mathematical way to describe this scaling behavior.

The Search for the Dominant Term

When we analyze an algorithm, we look for the operation that takes the most time as the input, which we call $n$ , gets infinitely large. This is called the dominant term. If an algorithm takes $n^2 + 5n + 10$ steps, the $n^2$ part will completely overshadow the $5n$ and the $10$ when $n$ is a million. Big O isolates this dominant term, letting us say the algorithm is $O(n^2)$ .

Why We Drop the Constants

In Big O notation, we ignore constants and coefficients. An algorithm that takes $50n$ steps and one that takes $2n$ steps are both considered $O(n)$ , or linear time. This can feel weird at first. Why treat them the same? Because Big O only cares about the shape of the growth curve. Hardware speeds and language efficiencies change the constant multipliers, but an $O(n)$ algorithm will eventually always beat an $O(n^2)$ algorithm for large enough inputs, regardless of the constants.

Where Students Slip Up

The most common mistake is thinking Big O measures exact time in seconds or exact operations. A student might test their $O(n^2)$ code on 10 items, see it finishes in 0.001 seconds, and think it is perfectly efficient. But Big O is about scaling. If that same code runs on 100,000 items, the time doesn't scale linearly; it scales quadratically, and those 0.001 seconds could suddenly become hours.

Worked through

Determine the Big O time complexity of a function that takes an array of size $n$ , prints every item once, and then compares every item to every other item to check for duplicates.

First, we break down the operations. Printing every item in the array takes $n$ steps. Comparing every item to every other item requires a nested loop: for each of the $n$ items, we look at the other $n$ items. This takes $n imes n = n^2$ steps.

The total number of steps is $n^2 + n$ .

Next, we apply the rules of Big O notation. We look at what happens as $n$ gets very large. The $n^2$ term grows much faster than the $n$ term, making it the dominant term. We drop the smaller $n$ term.

Therefore, the time complexity is $O(n^2)$ .

Questions students ask

Ask about this topic

Explain at

Where this comes from: Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein) · Khan Academy: Algorithms Unit · Grokking Algorithms (Aditya Bhargava)