Big-O Notation Explained

I remember hating my algorithms class in college, and Big-O notation was part of the reason. I just never got it. It seemed completely disjointed from anything I could possibly do in real life. If that’s you as well, here’s an explanation that should clear it up for you.

How much harder does something get as you increase your input?

An algorithm is just a series of steps for solving a problem.

Big-O notation is a metric for algorithm scalability.

The entire point of Big-O notation is to be able to compare how efficiently one algorithm solves big problems compared to another.

So if you have a giant list of names, or phone numbers, or some other kind of input—what’s the best possible way of sorting them, or searching them, based on whether the list has 10 entries, or 100, or a million?

That’s what Big-O notation tells you. It tells you how well that particular approach will do against very large problems.

O(1)
/’oh won’/
constant complexity

No matter what you provide as input to the algorithm, it’ll still run in the same amount of time.

• 1 item, 1 second
• 10 items, 1 second
• 100 items, 1 second

Example: Determining if a binary number is even or odd.

It’s helpful to think of logarithms as exponents in reverse.

O(log n)
/’oh log en’/
logarithmic complexity

The calculation time barely increases as you exponentially increase the input numbers.

• 1 item, 1 second
• 10 items, 2 seconds
• 100 items, 3 seconds

Example: Binary search.

O(n)
/’oh en’/
linear complexity

The calculation time increases at the same pace as the input.

• 1 item, 1 second
• 10 items, 10 seconds
• 100 items, 100 seconds

Example: Unsorted list search.

Things raised to the second power are called quadratic because it comes from the Latin for “making square”, i.e., to multiply times itself.

O(n²)
/’oh en squared’/
quadratic complexity

The calculation time increases at the pace of n2.

• 1 item, 1 second
• 10 items, 100 seconds
• 100 items, 10,000 seconds

Example: Bubble sort.

N! is a bad place in the algorithm world. It means it’s basically unsolvable.

O(n!)
/’oh en factorial’/
factorial complexity

The calculation time increases at the pace of n!, which means if n is 5, it’s 5x4x3x2x1, or 120. This isn’t so bad at low values of n, but it quickly becomes impossible.

• N=1, 1 option
• N=10, 3,628,800 options
• N=100, 9.332621544×10¹⁵⁷ options

Example: Traveling salesman.

Summary

1. Algorithms are lists of steps for solving problems.
2. Some algorithms are good at problems when they’re small, but fail at scale, e.g., with very long lists of things to sort or search.
3. Big-O notation is the way to tell how good a given algorithm is at solving very large problems.

Notes

1. There are other Big-O notation types as well, but these are the major ones. Link