Time Complexity

Time complexity models how an algorithm's operation count grows with a declared input measure. It predicts scaling under an abstract cost model; it does not replace measurement of an implementation on representative hardware and data.

State the model

Before simplifying a bound, identify:

• what $n$ means, or whether several parameters such as $V$ and $E$ matter;
• which operations are treated as constant time;
• worst, average, expected, amortized, or output-sensitive behavior;
• assumptions about representation, ordering, randomness, and numeric bit size.

For example, BFS is $O(V+E)$ with adjacency lists, not merely $O(V)$, while an algorithm polynomial in a numeric capacity may be pseudo-polynomial in encoded input length.

Asymptotic notation

• $T(n)=O(f(n))$: an eventual upper bound.
• $T(n)=\Omega(f(n))$: an eventual lower bound.
• $T(n)=\Theta(f(n))$: matching upper and lower bounds.

Big-O is not a synonym for “worst case.” Case analysis and asymptotic notation are separate: one may state an expected $\Theta(n\log n)$ runtime or a worst-case $O(n^2)$ bound.

Analysis patterns

• Consecutive phases add; the dominant growing term often controls the result.
• Nested work multiplies only when the inner cost applies for each outer step.
• Halving or doubling an interval usually produces logarithmic depth.
• Recursive algorithms require a recurrence or an accounting argument.
• Enumeration must include output size: producing $n!$ permutations cannot take sub-factorial total output time.

Common growth classes

$$1 < \log n < n < n\log n < n^2 < c^n < n! \qquad(c>1)$$

This ordering is asymptotic. Constants, cache behavior, vectorization, allocation, and input distribution still determine practical crossover points.

Quantifiers and worked counts

For eventually nonnegative functions, $T(n)=O(f(n))$ means that constants $c>0$ and $n_0$ exist such that $T(n)\leq c f(n)$ for every $n\geq n_0$. They must not grow with $n$. For $T(n)=3n^2+2n+7$ and $n\geq1$, $3n^2\leq T(n)\leq12n^2$, proving $\Theta(n^2)$, not just an upper bound.

def pair_count(n):
    count = 0
    for i in range(n):
        for j in range(i):
            count += 1
    return count

assert pair_count(4) == 6
assert pair_count(0) == 0

For nonnegative integer n, the inner body runs $\sum_{i=0}^{n-1}i=n(n-1)/2$ times. If instead an inner variable doubles from 1 while below n, there are $\lceil\log_2 n\rceil$ iterations for $n\geq1$. Repeating that entire inner loop for each of $n$ outer steps costs $\Theta(n\log n)$, not $\Theta(n^2)$ merely because two loops are nested.

Best, worst, average, expected, amortized

Best and worst take the minimum and maximum over inputs of a fixed size. Average case takes an expectation over a declared input distribution. Randomized expected cost averages over the algorithm's random choices, possibly for any fixed input. These are different sources of randomness.

Amortized cost needs no probability model: it bounds the total cost of an operation sequence. Consider an initially empty dynamic array whose capacity starts at one and doubles when full. Across $m$ appends, copying at resizes costs $1+2+4+\cdots<2m$, and the new writes cost $m$. Total work is $O(m)$, so an append costs amortized $O(1)$ even though one resize costs $\Theta(m)$. For eight appends, copied slots total $1+2+4=7$ and new writes total eight. Growing capacity by only one instead copies $1+2+\cdots+(m-1)$ slots and loses the constant amortized bound. This argument counts reference-slot operations, not arbitrary-size integer arithmetic, expensive comparisons, or wall-clock latency.

Source

• MIT OpenCourseWare: Asymptotic Complexity

My reading · Opened notes are remembered in this browser.