Big-O notation

Big-O is a way to describe how fast an algorithm’s work grows as the input gets bigger.

The core idea

Big-O ignores the small stuff and keeps the shape.

If one algorithm does about steps, and another does about steps, they are both linear: as grows, the work grows in proportion to . Big-O cares about that growth pattern, not the exact stopwatch time .

The practical question is simple:

When the input doubles, does the work stay about the same, double, square, or explode?

The handful of patterns that matter

• — constant. The work stays roughly the same no matter how big the input gets.

• — logarithmic. The problem shrinks fast; each step cuts the search space down.

• — linear. More input means proportionally more work.

• — linearithmic. Slightly worse than linear; common in efficient sorting.

• — quadratic. Work grows like “compare everything with everything.”

• or — exponential / factorial. Fine for tiny inputs, disastrous for large ones .

How to picture it

Think of input size as the width of the problem, and Big-O as the shape of the curve:

• Flat line:

• Slow bend upward:

• Straight slope:

• Steeper curve:

• Rocket launch:

That is why Big-O matters. At small sizes, different algorithms can feel similar. At large sizes, the curve wins.

One subtle but important thing

Big-O is an upper bound on growth: it says the algorithm grows no worse than some rate for large enough inputs .

Related notation:

• Big-Omega : a lower bound

• Big-Theta : a tight bound, meaning the growth is pinned from both sides

In everyday programming talk, though, people often say “Big-O” when they really mean “the algorithm’s growth rate.”