Common Runtimes

Constant functions

A constant function f(n) = c produces the same output regardless of n. In algorithms, this occurs when the work required does not depend on input size. Accessing an array element by index is constant because the memory address calculation takes the same time whether the array has 10 elements or 10 million.

Logarithmic functions

The logarithm log_b(n) asks: "How many times must I multiply b to reach n?" Equivalently: "How many times can I divide n by b before reaching 1?" For binary logarithms (base 2):

• log₂(2) = 1

• log₂(4) = 2

• log₂(8) = 3

• log₂(1024) = 10

• log₂(1,000,000) ≈ 20

Logarithms grow incredibly slowly. Doubling n adds only 1 to log₂(n). This is why logarithmic algorithms scale so well.

Linear functions

A linear function f(n) = cn grows proportionally with n. Double the input, double the work. This is the natural complexity for problems requiring examination of every element once.

Linearithmic functions

The function n log n appears when an algorithm must do logarithmic work for each of n elements, or when divide-and-conquer splits the problem and performs linear work at each level. It grows faster than linear but much slower than quadratic.

Polynomial functions

Polynomials like n², n³, and n⁴ arise from nested iteration. Two nested loops over n elements typically produce O(n²). Three nested loops produce O(n³). The exponent equals the depth of nesting.

Exponential functions

Exponential functions like 2ⁿ grow by a constant factor for each unit increase in n. They arise when an algorithm must consider all subsets of a set (2ⁿ subsets for n elements) or when recursive calls branch without combining subproblems.

Factorial functions

The factorial n! = n × (n-1) × (n-2) × ... × 1 counts the number of permutations of n elements. It grows even faster than exponential, making factorial algorithms impractical for n > 15 or so.

Direct access yields constant time

When data is stored at a known location, retrieving it requires only calculating that location. Arrays provide this property through pointer arithmetic. Hash tables provide it probabilistically through hash functions. Any data structure that maps keys directly to storage locations achieves constant time access.

Halving yields logarithmic time

Any algorithm that eliminates a constant fraction of remaining possibilities at each step exhibits logarithmic behavior. Binary search eliminates half. Ternary search eliminates two-thirds. The specific fraction affects only the constant factor, not the complexity class. The key insight is that reaching one element from n requires only log(n) halvings.

Full traversal yields linear time

When an algorithm must examine every element at least once, it cannot be faster than linear. Finding the sum, the maximum, or verifying a property across all elements requires O(n) time. This is often the best achievable complexity for problems that depend on all input data.

Divide and conquer with linear merge yields linearithmic time

Algorithms that split the problem in half, solve both halves recursively, and combine results in linear time achieve O(n log n). The recursion has log(n) levels, and each level does O(n) total work. Merge sort is the canonical example.

Pairwise comparison yields quadratic time

When an algorithm must consider every pair of elements, it performs n × n work. Even if symmetry reduces this to n(n-1)/2, this is still O(n²). Matrix operations, naive duplicate detection, and simple sorting algorithms exhibit this pattern.

Subset enumeration yields exponential time

When an algorithm must consider all possible combinations of including or excluding each element, it faces 2ⁿ possibilities. Each element contributes a binary choice, and n independent binary choices produce 2ⁿ outcomes.

Permutation enumeration yields factorial time

When an algorithm must consider all possible orderings, it faces n! possibilities. The first position has n choices, the second has n-1, and so on.

Time budgets for different complexities

Understanding practical limits helps you make algorithmic decisions before implementation:

For interactive applications (response within 100ms):

• O(1): unlimited

• O(log n): unlimited

• O(n): up to ~10⁷

• O(n log n): up to ~10⁶

• O(n²): up to ~3,000

• O(n³): up to ~500

For batch processing (response within 1 hour):

• O(1): unlimited

• O(log n): unlimited

• O(n): up to ~10¹¹

• O(n log n): up to ~10¹⁰

• O(n²): up to ~6 × 10⁵

• O(n³): up to ~15,000

• O(2ⁿ): up to ~45

These estimates assume modern hardware and well-implemented algorithms. Real performance varies based on constant factors, memory access patterns, and implementation quality.

The computational cliff

Consider what happens as n increases from 50 to 100:

Polynomial complexities grow by small constant factors. Exponential complexity grows by a factor larger than all the atoms in the observable universe. This is not a quantitative difference but a qualitative one: polynomial problems are solvable; exponential problems often are not.

Implications for problem solving

The tractability divide affects how you approach problems:

For polynomial problems:

• Focus on reducing the exponent (O(n³) → O(n²) → O(n))

• Optimize constant factors for performance

• Expect the algorithm to scale with better hardware

For exponential problems:

• Determine if exact solutions are necessary

• Consider approximation algorithms with proven bounds

• Apply heuristics that work well in practice

• Use pruning to eliminate impossible solutions early

• Accept that input size limits are fundamental, not temporary

Constant factors matter

Big-O notation deliberately hides constant factors because they do not affect growth rate. However, constant factors significantly impact real performance:

• An algorithm performing 100n operations is 100 times slower than one performing n operations, despite both being O(n).

• Cache-friendly memory access can provide 10-100× speedups over cache-unfriendly access.

• Predictable branching patterns enable CPU speculation, improving performance by 2-5×.

For algorithms in the same complexity class, the faster one in practice depends on:

• Constant factors in the operation count

• Memory access patterns (sequential vs. random)

• Branch predictability

• Parallelization potential

• Language and runtime efficiency

When lower complexity loses

A higher-complexity algorithm can outperform a lower-complexity one for specific input sizes:

• Binary search (O(log n)) has overhead that makes linear search (O(n)) faster for arrays under 10-50 elements.

• Hash table insertion (O(1) amortized) involves overhead that makes array insertion faster for very small collections.

• Quick sort (O(n log n) average) often beats merge sort (also O(n log n)) due to better cache behavior, despite worse worst-case complexity.

The crossover point where theoretical complexity dominates depends on implementation details and hardware characteristics.

Cache-friendly algorithms

Sequential memory access is fast because processors fetch data in cache lines (typically 64 bytes). Accessing element i+1 after element i often costs nothing because it is already cached.

Random memory access is slow because each access potentially requires fetching a new cache line. An algorithm that jumps around memory pays the full latency cost repeatedly.

This is why:

• Array-based data structures often outperform pointer-based ones

• Merge sort can be slower than quick sort despite similar complexity

• Hash tables with open addressing outperform those with chaining for small load factors

Working set size

An algorithm's working set is the amount of memory it actively uses. When the working set fits in cache, performance is excellent. When it exceeds cache size, performance degrades sharply.

This creates effective complexity thresholds:

• n ≤ 10,000: Most data fits in L3 cache; algorithms run at near-theoretical speed

• n ≤ 1,000,000: Data exceeds L3 cache; memory bandwidth becomes limiting

• n ≤ 100,000,000: Data exceeds main memory; disk access dominates

These thresholds shift the practical limits of each complexity class.

Time-space tradeoffs

Many algorithmic improvements trade space for time:

• Hash tables: O(n) space enables O(1) lookups instead of O(n)

• Dynamic programming: O(n) or O(n²) space can reduce exponential time to polynomial

• Precomputation: O(n) space for lookup tables reduces repeated computation

The optimal tradeoff depends on available memory and access patterns.

In-place algorithms

An in-place algorithm uses O(1) extra space beyond the input. These algorithms are valuable when memory is constrained:

• In-place sorting (heap sort, quick sort) requires only O(log n) stack space

• In-place array reversal uses O(1) extra space

• In-place matrix transposition uses O(1) extra space

In-place algorithms are often more complex to implement but essential for large-scale data processing.

When amortized analysis matters

Amortized complexity is appropriate when:

• Operations are performed in sequences, not individually

• Occasional expensive operations are acceptable

• You care about total time, not individual operation time

Amortized complexity is problematic when:

• Real-time guarantees are required

• Operations are latency-sensitive

• Expensive operations cause unacceptable delays

Worst-case complexity

The maximum time for any input of size n. This is the most common measure because it provides guarantees:

• Quick sort is O(n²) worst case (when pivot selection is poor)

• Binary search is O(log n) worst case

• Hash table lookup is O(n) worst case (when all keys collide)

Worst-case analysis is conservative but safe.

Average-case complexity

The expected time over all possible inputs of size n, assuming some probability distribution:

• Quick sort is O(n log n) average case (random pivot selection)

• Hash table lookup is O(1) average case (uniform hash distribution)

• Linear search is O(n/2) = O(n) average case (target equally likely anywhere)

Average-case analysis is realistic but requires assumptions about input distribution.

Best-case complexity

The minimum time for any input of size n:

• Insertion sort is O(n) best case (already sorted)

• Linear search is O(1) best case (target is first)

• Binary search is O(1) best case (target is middle)

Best-case analysis is optimistic and rarely useful for algorithm selection.

Which case matters?

For algorithm selection, prioritize cases in this order:

1. Worst case when inputs may be adversarial or pathological cases are common

2. Average case when inputs are random or well-distributed

3. Best case rarely, only when inputs are known to have special structure

Web applications

• Response time budget: 100-500ms

• Typical data sizes: 100 to 10,000 items per request

• Acceptable complexities: O(1) through O(n log n); O(n²) only for n < 1000

Data processing pipelines

• Response time budget: Minutes to hours

• Typical data sizes: Millions to billions of records

• Acceptable complexities: O(n) through O(n log n); O(n²) rarely acceptable

Scientific computing

• Response time budget: Hours to days

• Typical data sizes: Thousands to millions of elements (often matrices)

• Acceptable complexities: O(n³) for dense linear algebra; specialized algorithms for specific structures

Competitive programming

• Response time budget: 1-2 seconds

• Typical data sizes: Specified per problem (often 10⁵ to 10⁶)

• Target complexity: Usually deducible from constraints

Single loop over input: O(n)

A single loop that iterates once per element is O(n). Multiple sequential loops are still O(n) because O(n + n + n) = O(n).

Nested loops over input: O(n²)

Two nested loops, each iterating over input, produce O(n²). The outer loop runs n times; for each iteration, the inner loop runs up to n times.

Nested loops with shrinking range: Still O(n²)

Loops like "for i from 0 to n; for j from i to n" iterate n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 times. This is O(n²).

Halving the search space: O(log n)

Any loop that halves remaining work each iteration is O(log n). Binary search divides by 2; ternary search divides by 3. Both are O(log n).

Recursion with single recursive call: Depends on reduction

A recursive function making one call to a smaller problem has complexity depending on how much smaller:

• f(n) calls f(n-1): O(n) total calls

• f(n) calls f(n/2): O(log n) total calls

Recursion with multiple recursive calls: Often exponential

A recursive function making multiple calls without memoization often has exponential complexity:

• f(n) = f(n-1) + f(n-1): O(2ⁿ)

• f(n) = f(n-1) + f(n-2): O(1.618ⁿ) ≈ O(2ⁿ)

Memoization can reduce these to polynomial complexity.