Algorithm analysis: growth, bounds, and common patterns
Original teaching material prepared for the Knowable public sample.

Let n be the input size and T(n) the number of elementary operations performed by an algorithm. Operation counting assumes a stated computation model. In this lesson, array indexing, arithmetic on fixed-size values, and each call to process(item) are assumed to take constant work. An operation count is not a measurement in milliseconds. Actual execution time also depends on hardware, implementation, data representation, and input characteristics.

Big O gives an asymptotic upper bound. T(n) belongs to O(g(n)) if positive constants c and n0 exist such that 0 <= T(n) <= c*g(n) for every n >= n0. The threshold lets us ignore a finite initial range of inputs. Theta gives a tight asymptotic bound: T(n) belongs to Theta(g(n)) if positive constants c1, c2, and n0 exist such that c1*g(n) <= T(n) <= c2*g(n) for every n >= n0. Omega gives an asymptotic lower bound using T(n) >= c*g(n). These bounds describe growth; they do not independently specify best, average, or worst case. State which case is being analyzed. A linear function can belong to both O(n) and O(n^2), but Theta(n) states its tight growth class.

For T(n) = 3n + 2 and n >= 1, 3n + 2 <= 5n, so c = 5 and n0 = 1 establish O(n). It is also at least 3n, which establishes Theta(n). Positive constant factors and lower-order terms do not change this growth class. In a polynomial, the highest-degree nonzero term controls asymptotic growth. Constants still matter to performance at finite input sizes; asymptotic notation is not an excuse to ignore actual measurements.

Typical tight growth classes, assuming the stated constant-cost operations, are Theta(1) for array indexing, Theta(log n) for repeatedly halving a positive search interval, Theta(n) for visiting all n items, Theta(n log n) for standard merge sort, and Theta(n^2) for two full nested loops that each run n times. Logarithm bases greater than one differ only by a constant factor, so log base 2 and natural log have the same asymptotic class.

Illustrative operation counts, not benchmark times: for n = 8, n = 16, and n = 32, the values of 1 are 1, 1, 1; log2(n) values are 3, 4, 5; n values are 8, 16, 32; n*log2(n) values are 24, 64, 160; and n^2 values are 64, 256, 1024. Doubling n doubles n and quadruples n^2, while log2(n) grows by one. These figures compare functions, not the actual running times of different programs.

A single full loop has n calls to process:
for item in items:
    process(item)
Under the constant-work assumption, its work is Theta(n). Two consecutive full loops require n + n = 2n calls and remain Theta(n). Multiplication applies to repeated nesting, not merely to having two loops in the program.

Two full nested loops have n*n calls:
for i in range(n):
    for j in range(n):
        process((i, j))
Their work is Theta(n^2). A triangular loop, where j ranges from 0 to i-1, has 0 + 1 + ... + (n-1) = n(n-1)/2 calls, also Theta(n^2). A loop inside another loop does not automatically imply quadratic growth: the inner iteration count and its cost matter. If an inner loop always runs five times, its total work is Theta(n).

Binary search requires a sorted random-access sequence. Each comparison discards roughly half the remaining candidates. An interval of size 16 can shrink through sizes 16, 8, 4, 2, and 1. A typical implementation then performs one final comparison; the number of comparisons depends on the stopping condition. Worst-case time is Theta(log n) when each comparison and index access has constant cost. Best-case time is Theta(1) when the first midpoint matches. The standard O(log n) search claim excludes the cost of initially sorting an unsorted input. Iterative binary search uses Theta(1) auxiliary space.

Merge sort repeatedly splits an input into two halves, recursively sorts both halves, and merges the results. Merging n total items takes Theta(n) work. There are Theta(log n) levels, each with Theta(n) total work, giving Theta(n log n) time for the standard implementation. A typical array-based implementation uses Theta(n) auxiliary storage for merging; its recursion stack uses Theta(log n) additional space. Time and auxiliary space should be reported separately. Input storage is normally excluded from auxiliary-space analysis unless stated otherwise.

A practical analysis workflow is to define n, choose the case, state the elementary-operation cost assumptions, count repetitions, combine consecutive work by addition and repeated nested work by multiplication, simplify the dominant growth, and separately check auxiliary space and prerequisites. A theoretically better growth class is useful for large inputs, but cannot guarantee that one implementation will be faster for every finite input.

Self-check exercises: (1) Classify 3n + 2 tightly: Theta(n). (2) Compare two consecutive full loops with two full nested loops: Theta(n) versus Theta(n^2), respectively. (3) Count triangular loop calls for n = 4: 0 + 1 + 2 + 3 = 6. (4) Explain why searching an unsorted array is not automatically logarithmic: binary search requires sorted order, and preparing that order has its own cost. (5) Explain why O(n^2) can be a correct but loose upper bound for a linear algorithm: Big O need not be tight. (6) Report iterative binary search worst-case time and auxiliary space: Theta(log n) time and Theta(1) space, under the assumptions above.