Big O Notation — The Basics

Big O notation answers one question: as the input gets bigger, how much slower does the algorithm get?

We don't measure exact time because exact time depends on your CPU, your programming language, what else is running, and a dozen other factors. Instead, we measure growth rate — how the number of steps scales as the input size grows.

If an algorithm always takes the same number of steps no matter how big the input is, it's O(1) — constant time — meaning it's always fast no matter how many items you have. If it takes roughly one step per item, it's O(n) — linear time. If it takes roughly n × n steps, it's O(n²) — quadratic time.

This matters a lot. An O(n) algorithm on 1 million items might take 1 second. An O(n²) algorithm on the same input could take over 11 days.

The Five Complexity Classes You Must Know

O(1) — Constant Time

O(1) — constant time — means it's always fast no matter how many items you have. The number of steps never changes.

function getFirst(array):
    return array[0]     // always 1 step

Whether the array has 10 elements or 10 million, reading index 0 is one step.

O(n) — Linear Time

O(n) — linear time — means the work grows in proportion to the input. If the input doubles, the work doubles.

function findMax(array):
    max = array[0]
    for each item in array:
        if item > max:
            max = item
    return max

One pass through all n elements = O(n).

O(n²) — Quadratic Time

O(n²) — quadratic time — usually comes from a loop inside a loop. If the input doubles, the work quadruples.

function hasDuplicate(array):
    for each item A in array:
        for each item B in array (after A):
            if A == B:
                return true
    return false

For every element, you check every other element. That's n × n steps.

O(log n) — Logarithmic Time

O(log n) — logarithmic time — means the input is cut in half at each step. Even with a million items, you only need about 20 steps.

function binarySearch(sortedArray, target):
    low = 0
    high = length(sortedArray) - 1
    while low <= high:
        mid = (low + high) / 2
        if sortedArray[mid] == target:
            return mid
        else if sortedArray[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Each step cuts the remaining search space in half. You can only halve a million items about 20 times before you're down to 1.

O(n log n) — Linearithmic Time

O(n log n) is what you get from efficient sorting algorithms like merge sort. It's much better than O(n²) and only slightly worse than O(n).

Rules for Calculating Big O

Rule 1: Drop constants. O(3n) is just O(n). We care about the shape of the growth, not the exact multiplier.

// Two separate loops — still O(n), not O(2n)
for i = 0 to n:
    doSomething(i)
for j = 0 to n:
    doSomethingElse(j)

Rule 2: Drop smaller terms. O(n² + n) is just O(n²). As n grows large, n² completely dominates n.

Rule 3: One loop = O(n).

for i = 0 to n:    // O(n)
    doWork()

Rule 4: Nested loops multiply.

for i = 0 to n:        // outer: n times
    for j = 0 to n:    // inner: n times each
        doWork()        // total: n × n = O(n²)

Rule 5: Halving = O(log n).

while n > 1:       // O(log n)
    n = n / 2

Rule 6: Sequential sections — take the biggest.

for i = 0 to n:       // O(n)
    doA()
​
for i = 0 to n:       // O(n²) for this section
    for j = 0 to n:
        doB()
​
// Overall: O(n) + O(n²) = O(n²)

Comparison Table

Example 1: Counting the operations

function sumAndProduct(array):
    sum = 0
    for each item in array:       // n steps
        sum = sum + item
​
    product = 1
    for each item in array:       // n steps
        product = product * item
​
    return (sum, product)
​
// Two loops, each n steps = 2n → drop constant → O(n)

Example 2: A loop that looks quadratic but isn't

function printPairs(array):
    for i = 0 to length(array) - 1:
        for j = i + 1 to length(array) - 1:
            print(array[i], array[j])
​
// The inner loop gets shorter each time, but it still runs
// roughly n²/2 times total — drop the constant → O(n²)