Algorithm Analysis and Complexity Classes

Algorithm analysis establishes how an algorithm’s resource requirements grow with its input. It supports design decisions before implementation details, hardware, and representative workloads obscure the dominant cost. A useful analysis identifies the input size, specifies the resource, and states the cost model before deriving a bound.

Defining the Cost #

Choose a size parameter that represents the input. An array algorithm often uses \(n\), whereas a graph algorithm needs both its vertices \(V\) and edges \(E\). State the resource as well: comparison count, memory consumption, disk I/O, network round trips, or elapsed time under a defined machine model.

The RAM model treats arithmetic, comparison, indexing, and pointer operations on word-sized values as constant-time operations. That assumption makes the model suitable for in-memory algorithms, whereas external-memory algorithms must count block transfers because random disk access does not have constant cost.

Asymptotic Notation #

Asymptotic notation compares non-negative cost functions as their input grows. Constant factors and lower-order terms are omitted because they do not change the growth class.

• \(f(n) \in O(g(n))\) when constants \(c > 0\) and \(n_0\) exist such that \(f(n) \leq c g(n)\) for every \(n \geq n_0\). Big O provides an asymptotic upper bound.
• \(f(n) \in \Omega(g(n))\) when \(g(n) \in O(f(n))\). Big Omega provides an asymptotic lower bound.
• \(f(n) \in \Theta(g(n))\) when both relations hold. Big Theta provides a tight asymptotic bound.

For example, \(3n^2 + 10n + 4\) is \(\Theta(n^2)\). Binary search makes \(O(\log n)\) comparisons in a sorted array, while breadth-first search of an adjacency-list graph takes \(\Theta(V + E)\) time. A bound without its measured resource can be misleading: a comparison-based sort can use \(O(n \log n)\) comparisons while still requiring \(O(n)\) auxiliary memory.

Analyzing Iterative Algorithms #

Count the work performed by each loop and sum it across all iterations. Consecutive loops add their costs, whereas nested loops multiply only when every iteration of one executes every iteration of the other.

#include <cstddef>
#include <vector>

std::size_t lower_bound_index(const std::vector<int>& values, int target) {
    std::size_t first = 0;
    std::size_t last = values.size();

    while (first < last) {
        const std::size_t middle = first + (last - first) / 2;
        if (values[middle] < target) {
            first = middle + 1;
        } else {
            last = middle;
        }
    }
    return first;
}

The search interval is at least halved on every iteration. Therefore its running time is \(O(\log n)\), and its iterative implementation uses \(O(1)\) auxiliary space. Loop bounds that depend on a previous loop variable require a summation; for example, \(\sum_{i=1}^{n} i = \Theta(n^2)\).

Recurrences and Divide-and-Conquer #

Recursive algorithms often produce a recurrence. Merge sort divides an input into two halves and performs linear merging, giving:

The recursion has \(\log_2 n\) levels, and each level performs \(\Theta(n)\) work. Thus merge sort runs in \(\Theta(n \log n)\) time. Recursion trees expose this structure directly. For recurrences of the form \(T(n) = aT(n / b) + f(n)\), the Master Theorem classifies the result by comparing \(f(n)\) with \(n^{\log_b a}\); use a recursion tree or substitution proof when its preconditions do not apply.

Worst-Case, Expected, and Amortized Costs #

Worst-case analysis bounds every input of a given size. It provides a reliable capacity limit, although the worst input can be rare. Average-case analysis requires an explicit input distribution; absent such a distribution, calling a bound “average” has no mathematical meaning.

Expected analysis covers randomized algorithms. Randomized quicksort has expected \(\Theta(n \log n)\) running time when its pivot selection avoids adversarial order, even though a particular execution can take \(\Theta(n^2)\).

Amortized analysis bounds a sequence of operations without assuming an input distribution. Appending to a geometrically growing std::vector occasionally reallocates and copies \(\Theta(n)\) elements, but each element is copied only a bounded number of times. A sequence of appends therefore costs \(O(1)\) amortized time per append. Aggregate, accounting, and potential methods are equivalent ways to prove such bounds.

Decision Problems and NP-Completeness #

A decision problem has a yes-or-no answer. Complexity classes are defined over decision problems because polynomial-time reductions preserve those answers.

A language belongs to P when a deterministic machine decides it in polynomial time. A language belongs to NP when every yes instance has a certificate that a deterministic machine can verify in polynomial time. Consequently, \(P \subseteq NP\).

A problem is NP-hard when every problem in NP has a polynomial-time reduction to it. It is NP-complete when it is both NP-hard and in NP. An NP-completeness proof needs:

1. a polynomial-time verifier that establishes membership in NP; and
2. a polynomial-time reduction from a known NP-complete problem.

The question whether \(P = NP\) remains open. NP-completeness does not imply that practical instances are unsolvable; problem structure, parameter bounds, approximation algorithms, and heuristics can make specific instances tractable.