What Is Big O Notation: Simple Examples and Growth Charts

What Is Big O

Big O notation describes how an algorithm’s runtime or memory usage changes as the input size grows. It does not tell us the exact number of milliseconds. Instead, it gives us a useful way to compare the shape of growth: does the work stay flat, grow linearly, grow quadratically, or explode much faster?

Why Big O Matters

Understanding Big O helps you:

Compare different algorithms that solve the same problem.

Predict how code behaves as data gets larger.

Find parts of a program that may become bottlenecks.

Choose data structures and algorithms before performance becomes expensive.

O(1) Constant time

Accessing an array item by index. The input size barely matters.

O(log₂n) Logarithmic time

Binary search: each step removes half of the remaining options.

O(n) Linear time

A single pass over a list: twice as much data means roughly twice as much work.

O(n × log₂n) Efficient sorting

A common complexity for good sorting algorithms, such as quicksort on average.

O(n²) Quadratic time

Nested loops: comparing every item with every other item.

O(n!) Factorial time

Trying every permutation. It grows so fast that even small inputs can be dangerous.

Growth Chart

The chart below is not about exact milliseconds. The point is the direction: how quickly the number of operations increases as n grows.

O(log₂n)

Base 2: each step cuts the remaining work in half.

O(n)

Work grows at the same pace as the input.

O(n × log₂n)

More than linear, but still practical for sorting.

O(n²)

Nested-loop growth. Small inputs hide the cost.

O(2ⁿ)

Looks quiet, then rises sharply.

O(n!)

Trying every order. It becomes unusable very quickly.

Intuition Through Examples

Complexity	Idea	Example	What to remember
`O(log₂n)`	Each step sharply reduces the search space.	Binary search in a sorted list.	A million items becomes roughly 20 steps.
`O(n)`	You need to look at each item once.	Finding the smallest number in an array.	The growth is predictable and often acceptable.
`O(n × log₂n)`	Data is split into parts and then combined.	Efficient sorting.	Usually a good sign for sorting algorithms.
`O(n²)`	For each item, another pass runs inside.	Comparing every user with every other user.	It gets painful quickly on larger data sets.
`O(n!)`	Every possible permutation is checked.	Trying every route through a set of cities.	You almost always need a heuristic or a different approach.

Quick Notes

Big O describes growth, not exact time. Two `O(n)` algorithms may run at different speeds, but both grow linearly as input grows.

Constants are usually dropped. `O(2n)` becomes `O(n)` because the long-term growth pattern matters most.

Pay attention to the scenario. Some algorithms have different best-case, average-case, and worst-case behavior.