Common growth functions

Constant time: the cost does not depend on n. Array index access, HashMap.get on average, pushing onto a stack, reading a field. Constant does not mean fast: a single operation can still cost milliseconds.

Amortised O(1) (for example ArrayList.add) means O(1) on average over a long sequence of operations.

1int first = a[0];                  // O(1)
2int top = stack.peek();            // O(1)
3boolean has = set.contains(x);     // O(1) average

Logarithmic: each step discards a constant fraction of the remaining work, usually half. Binary search, balanced-tree lookups, heap push and pop and fast exponentiation. For n = 10⁹ that is about 30 steps.

Compare it with linear on the chart: the log curve is almost flat.

1int lo = 0, hi = a.length - 1;
2while (lo <= hi) {                  // at most floor(log2 n) + 1 iterations
3    int mid = lo + (hi - lo) / 2;
4    if (a[mid] < target) lo = mid + 1; else hi = mid - 1;
5}

Square-root time: trial division to test primality (loop while i·i ≤ n), square-root decomposition of arrays, and Mo's algorithm. For n = 10¹² it is only 10⁶ steps.

It sits between logarithmic and linear.

1static boolean isPrime(long n) {
2    if (n < 2) return false;
3    for (long i = 2; i * i <= n; i++) if (n % i == 0) return false;   // at most sqrt(n) iterations
4    return true;
5}

Linear: one pass over the input, with constant work per element. Linear search, finding the maximum, summing, counting, a single BFS/DFS over a tree, two-pointer scans. About 10⁸ simple linear steps fit in a second.

Reading the input is already linear, so no algorithm that must look at every element can beat it.

1long sum = 0;
2for (int x : a) sum += x;   // exactly n iterations

Linearithmic: n items with a logarithmic step each, or log n levels with n work per level. Merge sort, heap sort, quick sort on average, building a sorted structure with n tree or heap insertions. It is the target for sorting, and is comfortable for n up to a few million.

n log₂ n is about 2 × 10⁷ at n = 10⁶.

1Arrays.sort(a);                         // O(n log n)
2PriorityQueue<Integer> pq = new PriorityQueue<>();
3for (int x : a) pq.offer(x);            // n pushes of O(log n) each

Quadratic: two nested loops over the input, or all pairs. Bubble, selection and insertion sort, naive pair counting and the simple DP over two strings. Usable up to about n = 5,000 to 10,000 in a second.

Doubling n multiplies the time by four.

1int pairs = 0;
2for (int i = 0; i < n; i++)
3    for (int j = i + 1; j < n; j++)
4        if (a[i] + a[j] == target) pairs++;   // n(n-1)/2 checks

Cubic: three nested loops or a triple over the input. Naive matrix multiplication, Floyd-Warshall, and the straightforward interval DP. Practical only up to n of a few hundred.

Doubling n multiplies the time by eight.

1for (int k = 0; k < n; k++)
2    for (int i = 0; i < n; i++)
3        for (int j = 0; j < n; j++)
4            d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);   // Floyd-Warshall, n^3

Exponential: the cost doubles with each extra input element. Enumerating every subset, naive Fibonacci recursion (about φⁿ), and brute-force search over binary choices. Feasible to n ≈ 20 to 25.

Dynamic programming and pruning exist to avoid it; bitmask DP brings many n! problems down to O(2ⁿ · n).

1int n = 20; long count = 0;
2for (int mask = 0; mask < (1 << n); mask++) count += Integer.bitCount(mask);   // visits 2^n subsets

Factorial: the cost is the number of orderings, n!. Brute-force travelling salesman and generating all permutations. n = 10 gives 3,628,800 and n = 13 gives 6,227,020,800, so it is feasible only to about n = 10 or 11.

n! grows faster than any exponential cⁿ.

1static long permutations(int n) {      // counts what a permutation generator would visit
2    long f = 1;
3    for (int i = 2; i <= n; i++) f *= i;
4    return f;                          // 10! = 3628800
5}

A polynomial algorithm costs O(nᵏ) for a fixed k; an exponential one costs O(cⁿ) with c > 1. The gap is decisive: at n = 50, n³ is 125,000 while 2ⁿ is about 1.1 × 10¹⁵. Problems with polynomial algorithms are considered tractable; NP-hard problems have no known polynomial algorithm.

Move n in the calculator and compare the time at 10⁹ operations per second.