- 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