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.

Source

• MIT OpenCourseWare: Asymptotic Complexity