- Unsupervised Learning
- Posts
- Big-O Notation Explained
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.
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.
1 item, 1 second
10 items, 2 seconds
100 items, 3 seconds
Example: Binary search.
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.
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.
N=1, 1 option
N=10, 3,628,800 options
N=100, 9.332621544×10157 options
Example: Traveling salesman.
Summary
Algorithms are lists of steps for solving problems.
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.
Big-O notation is the way to tell how good a given algorithm is at solving very large problems.
Notes
There are other Big-O notation types as well, but these are the major ones. Link