Big O and Time Complexity

Time complexity describes how the number of steps an algorithm takes grows as the input size n grows. It doesn't measure seconds, which depend on the machine. It measures growth, so you can compare two algorithms on paper.

Counting operations

Take a function that sums an array. The running total is a long, because an int total wraps around silently once it passes Integer.MAX_VALUE:

Java

public class Main {
    static long sum(int[] nums) {
        long total = 0;          // 1 step
        for (int x : nums) {     // runs n times
            total += x;          // 1 step each time
        }
        return total;            // 1 step
    }

    public static void main(String[] args) {
        System.out.println(sum(new int[]{3, 1, 4, 1, 5}));
    }
}

Output

The exact count is about n + 2 steps. For large n, the + 2 doesn't matter, and neither does whether a loop iteration costs 1 step or 3. Big O keeps only the part that grows fastest:

Drop constant factors: 3n + 5 becomes O(n).
Keep only the largest term: n² + 10n + 100 becomes O(n²).
Different inputs keep separate variables: two arrays of lengths n and m give O(n + m) or O(n·m), not O(n).

Unless stated otherwise, Big O means the worst case. Linear search is O(n) even though it sometimes finds the target at index 0.

Loops

Most of the time, the loops give you the answer.

Code shape	Steps	Big O
one loop over `n` items	`n`	`O(n)`
two loops one after another	`n + n`	`O(n)`
a loop inside a loop, both over `n`	`n · n`	`O(n²)`
inner loop starts at `i + 1`	`n(n-1)/2`	`O(n²)`
loop where the range halves each time	`log₂ n`	`O(log n)`
a halving loop inside a loop over `n`	`n · log n`	`O(n log n)`

Loops one after another add. Loops inside each other multiply.

Java

public class Main {
    static String examples(int[] nums) {
        // One loop over n items: O(n)
        long sum = 0;
        for (int x : nums) sum += x;

        // Nested loops over all pairs i < j: n(n-1)/2 checks, O(n²)
        int equalPairs = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[j]) equalPairs++;
            }
        }

        // The range halves every step: O(log n)
        int halvings = 0;
        int size = nums.length;
        while (size > 1) {
            size /= 2;
            halvings++;
        }

        return "(" + sum + ", " + equalPairs + ", " + halvings + ")";
    }

    public static void main(String[] args) {
        System.out.println(examples(new int[]{1, 2, 2, 3, 3, 3, 4, 5}));
    }
}

Output

(23, 4, 3)

The whole function is O(n) + O(n²) + O(log n), which is O(n²).

The "inner loop starts at i + 1" case is a common trap. It does about half the work of a full nested loop, but half of n² is still O(n²).

Logarithmic time

An algorithm is O(log n) when each step throws away a constant fraction of the remaining input. Binary search halves the range on every comparison, so a sorted array of 1,000,000 elements needs at most about 20 comparisons (2²⁰ ≈ 1,000,000).

Java

import java.util.stream.IntStream;

public class Main {
    // Returns the index of target, or -1 when it is absent.
    static int binarySearch(int[] nums, int target) {
        int lo = 0, hi = nums.length; // search in [lo, hi)
        int steps = 0;
        while (lo < hi) {
            steps++;
            int mid = lo + (hi - lo) / 2; // lo + hi could overflow int for huge arrays
            if (nums[mid] == target) {
                System.out.println("found after " + steps + " steps");
                return mid;
            } else if (nums[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = IntStream.range(0, 1_000_000).toArray();
        System.out.println(binarySearch(nums, 765_432));
    }
}

Output

found after 20 steps
765432

A nested loop is not always O(n²)

Count how many times the inner body runs in total, not how deeply the loops are nested. In this two-pointer loop, each step moves left or right inward, so the total work across both loops is O(n):

Java

public class Main {
    static boolean hasPairWithSum(int[] sorted, int target) {
        int left = 0, right = sorted.length;
        while (left + 1 < right) {
            int sum = sorted[left] + sorted[right - 1];
            if (sum == target) {
                return true;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(hasPairWithSum(new int[]{1, 3, 4, 6, 9}, 10));
    }
}

Output

true

The same reasoning applies to a monotonic stack: every element is pushed once and popped at most once, so a while loop inside a for loop can still be O(n) in total.

Hidden loops

A single line can hide a loop. These are all O(n) on an ArrayList (a resizable array-backed list):

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> v = new ArrayList<>(List.of(5, 1, 4, 2, 3));

        boolean hasFour = v.contains(4);        // scans the list
        v.add(0, 9);                            // shifts every element right
        v.remove(0);                            // shifts every element left (remove by index)
        List<Integer> copy = new ArrayList<>(v); // copies every element
        int max = Collections.max(v);           // scans the list
        String text = v.toString();             // visits every element

        System.out.println(hasFour + " " + copy + " " + max + " " + text);
    }
}

Output

true [5, 1, 4, 2, 3] 5 [5, 1, 4, 2, 3]

Calling v.contains(x) inside a loop over v is O(n²), even though only one loop is visible. The same goes for new ArrayList<>(v) or Arrays.copyOfRange(a, i, a.length) inside a loop, and for s += c on a String in a loop: strings are immutable, so each += copies the whole string, and n appends cost O(n²). A StringBuilder appends in amortized O(1). Sorting (Arrays.sort, List.sort) is O(n log n), so "sort, then loop once" is O(n log n) overall.

Recursion

For recursion, count the number of calls and multiply by the work per call. Each call also uses a stack frame, and the thread stack is limited, so very deep recursion (for example sumTo(1_000_000)) throws StackOverflowError.

Java

public class Main {
    // n calls, O(1) each: O(n)
    static long sumTo(long n) {
        return n == 0 ? 0 : n + sumTo(n - 1);
    }

    // Each call halves n: O(log n) calls
    static int countBits(long n) {
        return n == 0 ? 0 : 1 + countBits(n / 2);
    }

    // Each call makes two more calls: about 2ⁿ calls, O(2ⁿ)
    static long fib(int n) {
        return n < 2 ? n : fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) {
        System.out.println(sumTo(100) + " " + countBits(1_000_000) + " " + fib(20));
    }
}

Output

5050 20 6765

fib is slow because it solves the same subproblems again and again: fib(18) is computed twice, fib(17) three times, and so on. Remembering results (memoization) or looping upward brings it down to O(n).

A recursive function that visits every node of a tree once is O(n), no matter what shape the tree has.

Common complexity classes

Big O	Name	Typical example	n = 1,000,000
`O(1)`	constant	index an array, `HashMap.get` (expected), `ArrayDeque.push`	1
`O(log n)`	logarithmic	binary search, `PriorityQueue.add`	about 20
`O(n)`	linear	one pass over the input	10⁶
`O(n log n)`	linearithmic	`Arrays.sort`, `List.sort`	about 2·10⁷
`O(n²)`	quadratic	checking every pair	10¹² (too slow)
`O(2ⁿ)`	exponential	trying every subset	only works for small `n`, about 25
`O(n!)`	factorial	trying every ordering	only works for `n` up to about 11

Amortized O(1)

ArrayList.add usually writes into spare capacity in O(1). When the internal array is full, ArrayList allocates a larger array and copies every element, which costs O(n). The new capacity is a constant multiple of the old one, so the copies become rarer as the list grows, and n additions copy O(n) elements in total. Averaged over all additions, each one costs O(1). That's called amortized O(1).

When the final size is known, new ArrayList<>(n) allocates the capacity up front and avoids the reallocations.