Counting Steps: Big-O Made Simple

Don't time it – count it

A fast laptop and an old phone run the same code at different speeds, so seconds don't tell us much. Instead we ask: when the input gets bigger, how fast does the number of steps grow?

We call the input size n (for example, the number of items in an array). Big-O is just a short name for how the steps grow with n.

Let's count

Each method adds 1 to steps every time it does a basic piece of work:

public class Main {
    static long steps;

    static void constant(int n) {        // does not look at n at all
        steps++;
    }

    static void linear(int n) {          // one loop over n items
        for (int i = 0; i < n; i++) steps++;
    }

    static void quadratic(int n) {       // a loop inside a loop
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) steps++;
    }

    static void halving(int n) {         // n is cut in half each time
        while (n > 1) {
            n = n / 2;
            steps++;
        }
    }

    public static void main(String[] args) {
        int[] sizes = {10, 100, 1000};
        for (int n : sizes) {
            steps = 0; constant(n);  long c = steps;
            steps = 0; linear(n);    long l = steps;
            steps = 0; quadratic(n); long q = steps;
            steps = 0; halving(n);   long hv = steps;
            System.out.println("n=" + n + ": O(1)=" + c + "  O(log n)=" + hv + "  O(n)=" + l + "  O(n^2)=" + q);
        }
    }
}

Output

n=10: O(1)=1  O(log n)=3  O(n)=10  O(n^2)=100
n=100: O(1)=1  O(log n)=6  O(n)=100  O(n^2)=10000
n=1000: O(1)=1  O(log n)=9  O(n)=1000  O(n^2)=1000000

Look at what happens when n grows 10 times bigger:

• O(1) stays the same – like reading the first page of a book.
• O(log n) grows only a little – like finding a word in a dictionary by opening it in the middle.
• O(n) grows 10 times – like reading every page once.
• O(n²) grows 100 times – like comparing every page with every other page.

Two easy rules

Remember: 1) Keep only the biggest part: n² + n is just O(n²). 2) Ignore plain numbers: 3n + 7 is just O(n).

Tip: A simple guide: a computer does roughly 100 million simple steps per second. If your Big-O gives far more than that for the biggest input, you need a better algorithm.