Big O notation

Written Explanation

What Big O says

Big O describes how the number of steps grows with the input size n, ignoring details that do not change the shape of the growth. We write O(...) with the growth shape inside the brackets, and read it aloud as "order of" or "Big O of".

Take a method that does 3 steps for every element, plus 5 steps of setup. Its step count is 3n + 5. I ran such a method for three sizes on JDK 21:

Multiply n by 10 and the steps multiply by about 10. The setup is a rounding error and the factor 3 does not change the shape. This method is O(n), said "order n" or "linear".

The two simplification rules

1. Drop constant factors. 3n and 100n and n have the same shape: all grow in step with n. Write O(n).
2. Keep only the fastest-growing term. In n² + n, once n is large, n² dominates. For n = 1,000, n² is 1,000,000 and n is only 1,000, a tenth of a percent of the total. Write O(n²).

A fixed amount of work, like 100 steps whatever n is, is O(1): we write 1 for "a constant".

Big O is about large n. It deliberately ignores the cost of one step, which is why it never replaces a timing; it tells you the trend.

The five classes

log n here means the number of times you can halve n until you reach 1: about 3 for 10, about 10 for 1,000, about 20 for 1,000,000. We use base 2 in the examples, but the base does not matter in Big O, because changing the base only multiplies by a constant, and rule 1 drops constants.

Here is what the classes cost for three sizes. The values are exact arithmetic, rounded:

The order from slowest-growing (best) to fastest-growing (worst) is:

O(1) < O(log n) < O(n) < O(n log n) < O(n²)

Look at the last row. For a million items the quadratic column is a trillion steps, while n log n is twenty million. That gap is why we care about the class.

Reading code

Four small methods, each with a step counter added. I ran them for n = 10, 100, and 1,000.

static int first(int[] a) { steps++; return a[0]; }                       // O(1)

static int sum(int[] a) {                                                  // O(n)
    int s = 0;
    for (int x : a) { steps++; s += x; }
    return s;
}

static int halvings(int n) {                                               // O(log n)
    int c = 0;
    for (int i = n; i > 1; i /= 2) { steps++; c++; }
    return c;
}

static int pairs(int[] a) {                                                // O(n²)
    int c = 0;
    for (int i = 0; i < a.length; i++)
        for (int j = 0; j < a.length; j++) { steps++; if (a[i] == a[j]) c++; }
    return c;
}

n=10    first=1  sum=10    halvings=3  pairs=100
n=100   first=1  sum=100   halvings=6  pairs=10000
n=1000  first=1  sum=1000  halvings=9  pairs=1000000

Each column matches its class: constant, in step with n, one more step per doubling (roughly), and n × n.

What Big O does not say

• It does not give seconds. An O(n) method with a slow step can lose to an O(n²) method with a very fast step on tiny input.
• It does not say which of two methods in the same class is faster. Two O(n) loops can differ by a factor of ten.
• In everyday work Big O is quoted as the tightest simple class you can justify for the case you are discussing. Strictly, it is an upper bound on growth, a detail university texts treat formally. I did not fetch such a text for this lesson, so treat that sentence as background rather than a cited claim. L05 returns to cases.