Common Complexity Classes

Constant and logarithmic complexity

Some operations barely depend on the input size. For example, reading an array element at a known index requires the same kind of action whether the array contains ten elements or a million. This growth is denoted as O(1).

int first = numbers[0];

With O(log n), the number of steps grows very slowly: at each step, the part of the problem under consideration is usually reduced by a fixed factor. If the input doubles, the number of steps increases by roughly a constant amount.

Linear and linearithmic growth

O(n) commonly appears when the data is traversed once. If the input becomes ten times larger, the number of repetitions also grows by roughly a factor of ten.

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

O(n log n) grows faster than linear complexity but significantly slower than quadratic complexity. This class often appears in efficient sorting algorithms and in solutions that perform logarithmic work for many elements. It is useful to recognize the growth pattern itself even if the specific algorithm will be studied later.

Quadratic growth

O(n²) often appears when, for each element, a significant part of the same data must be examined again. A typical signal is two nested traversals over the input.

for (int left : numbers) {
    for (int right : numbers) {
        System.out.println(left + right);
    }
}

When n doubles, the number of pairs grows by roughly a factor of four. That is why the difference between O(n) and O(n²) becomes especially noticeable on large inputs.

Rapidly growing classes

There are algorithms with growth such as O(2ⁿ), O(n!), and even faster. They appear when a solution generates many combinations or possibilities, and even a small increase in the input sharply increases the amount of work. For small n, such an algorithm can still be practical, but it scales much worse than polynomial alternatives.

A useful ordering for comparing common classes is: O(1) → O(log n) → O(n) → O(n log n) → O(n²) → O(2ⁿ) → O(n!). This is not a list of “good” and “bad” algorithms, but a scale of how quickly their costs grow.