Algorithm Complexity and Big O Notation

Let’s talk about algorithm complexity, and how we measure it with Big O.

Different algorithms can solve the same problem with the same inputs. They can still take a very different amount of time.

That gap gets bigger as the input grows. Ten items might look fine. Ten thousand might not.

Big O describes how the cost grows as the input size grows. We call that size n.

Usually we care about the worst case. How bad can this get when things go wrong?

We also ignore constants and lower-order terms. 3n + 20 and n are both O(n). We care about the shape of the growth, not the exact milliseconds on your laptop.

The most common classes, from more efficient to less efficient, are:

• O(1)
• O(log n)
• O(n)
• O(n log n)
• O(n^2)
• O(2^n)
• O(n!)

n is the number of inputs. Sort 2 items and n is 2. Sort 20.000 items and n is 20.000.

You do not plug that number into the formula. O(n) is a label. It tells other developers how the algorithm scales.

O(1)

O(1) is constant time. The work does not grow with n.

Reading one item from an array by index is a classic example:

const scores = [12, 45, 67, 89, 91]
const first = scores[0]

Whether scores has 5 items or 5 million, that lookup still takes one step.

O(n)

O(n) scales linearly. Double the items, roughly double the work.

Summing every score in the array is O(n):

const scores = [12, 45, 67, 89, 91]

let total = 0
for (const score of scores) {
  total += score
}

One pass over the list. Ten items, about ten additions. A hundred items, about a hundred.

O(n^2)

O(n^2) grows much faster. Nested loops over the same list often land here.

Checking every pair of scores is a simple case:

const scores = [12, 45, 67, 89]

for (let i = 0; i < scores.length; i++) {
  for (let j = 0; j < scores.length; j++) {
    console.log(scores[i], scores[j])
  }
}

With 4 items you print 16 pairs. With 10 items you print 100. That squared growth is the whole point of the class.

O(log n) and O(n log n)

Two classes show up a lot, and they deserve a short intuition.

O(log n) means the work grows slowly because each step cuts the problem down. Binary search is the usual example: you look at the middle of a sorted list, throw away half, and repeat. A list of a million items needs only about 20 steps. I wrote a walkthrough of binary search in JavaScript if you want the code.

O(n log n) is what you get from many good comparison sorts, like merge sort or the average case of quicksort. You still touch every item (n), but you also do a logarithmic amount of dividing or combining work. That sits between linear O(n) and quadratic O(n^2), which is why it is the sweet spot for sorting large lists.

O(2^n)

O(2^n) is exponential. Generating every subset of a set is the classic example: add one item and the number of subsets doubles. A naive recursive Fibonacci lands in this class too. It sits between polynomial classes like O(n^2) and factorial O(n!).

Same class, different speed

Big O does not tell you everything. Two algorithms can share the same class and still feel different in practice, because constants, memory access and the shape of your real data all play a part. To compare those, you need to measure.

When the classes differ, the picture is clearer. An O(n) approach will beat an O(n^2) one as n grows, even if the quadratic version looks snappy on a tiny list.

Want me to talk about your product? You can sponsor this site.