Complexity Basics

Input size is the starting point

To talk about complexity, you first need to understand what exactly is growing. Input size is usually denoted by the letter n. For an array, this is usually the number of elements; for a string, the number of characters; and for a numeric problem, the input size depends on which data the algorithm actually processes.

After that, we estimate how much work is performed as n grows. The exact number of processor instructions is not the point; the growth pattern is. For example, one traversal of an array of length n performs an amount of work proportional to n.

boolean containsZero = false;

for (int value : numbers) {
    if (value == 0) {
        containsZero = true;
    }
}

If the array becomes twice as long, the loop will generally perform about twice as many iterations. This kind of growth is called linear and is written as O(n).

Why constants are usually dropped

Imagine that an algorithm traverses the same array twice:

for (int value : numbers) {
    System.out.println(value);
}

for (int value : numbers) {
    System.out.println(value * 2);
}

For an array of length n, this gives roughly 2n repetitions. But asymptotic analysis is interested in the shape of the growth, so a constant multiplier does not change the complexity class: O(2n) is written as O(n).

For the same reason, in an expression such as n * n + n, the quadratic term becomes dominant for large n. This complexity is written as O(n²).

Sequential work adds, nested work multiplies

A useful first rule is that independent sections of code executed one after another usually contribute a sum of costs, while nested repetitions contribute a product. For example, two separate linear loops still produce linear growth, while one loop inside another over the same n elements produces quadratic growth.

for (int i = 0; i < numbers.length; i++) {
    for (int j = 0; j < numbers.length; j++) {
        System.out.println(numbers[i] + numbers[j]);
    }
}

The inner action is performed for every pair of indices: roughly n * n times. That gives the estimate O(n²).