Asymptotic Analysis

Asymptotic analysis is the mathematical framework used to compare algorithms by how their running time or space complexity grows with input size $n$, especially for large $n$.2 Instead of focusing on exact machine-dependent timings, it emphasizes long-run growth rate and abstracts away constant factors and lower-order terms when they do not affect scalability.2

This perspective is essential because two algorithms may behave differently for small inputs yet reveal a consistent ordering for sufficiently large $n$. For example, an algorithm with runtime $100n$ can outperform one with runtime $n^2$ for small $n$, but the quadratic algorithm eventually grows faster and becomes less efficient as $n$ increases.

The main notational tools are Big-O for upper bounds, Big-Omega for lower bounds, and Big-Theta for tight bounds.2 These notations are used in algorithm analysis, proof of lower bounds, recurrence solving, and classification of computational efficiency.2

Footnotes

1. Asymptotic Notation: O(), o(), Ω(), ω(), and Θ() The Idea The Definitions - University of Arizona notes defining the standard asymptotic notations formally. ↩ ↩²

2. Recurrences, Master Theorem - University of Washington lecture notes connecting asymptotic analysis with case analysis and recursive algorithms. ↩ ↩²

3. What is Big O Notation Explained: Space and Time Complexity - Accessible summary of Big-O, Omega, Theta, and little-o definitions. ↩ ↩²

4. Lecture 16: Introduction to Asymptotic Analysis - Cornell lecture explaining simplification, growth comparison, and why asymptotic thinking focuses on large inputs. ↩ ↩² ↩³

5. Asymptotic Analysis and Recurrences - CMU lecture covering asymptotic notation, lower bounds, and recurrence-solving methods. ↩

Formal asymptotic notations

Let $f(n)$ and $g(n)$ be positive functions. Then the standard definitions are:2

• $f(n) \in O(g(n))$ if there exist constants $c>0$ and $n_0$ such that

  $$0 \le f(n) \le c\,g(n)\quad \text{for all } n \ge n_0$$

  So $g(n)$ is an asymptotic upper bound.

• $f(n) \in \Omega(g(n))$ if there exist constants $c>0$ and $n_0$ such that

  $$0 \le c\,g(n) \le f(n)\quad \text{for all } n \ge n_0$$

  So $g(n)$ is an asymptotic lower bound.2

• $f(n) \in \Theta(g(n))$ if there exist constants $c_1,c_2>0$ and $n_0$ such that

  $$0 \le c_1 g(n) \le f(n) \le c_2 g(n)\quad \text{for all } n \ge n_0$$

  This means $g(n)$ is a tight bound from both above and below.2

A useful interpretation is:

• $O(g(n))$: “at most this fast”
• $\Omega(g(n))$: “at least this fast”
• $\Theta(g(n))$: “grows at this rate asymptotically”2

Two additional notations appear in more mathematical treatments:

• little-o: $f(n)$ grows strictly slower than $g(n)$
• little-omega: $f(n)$ grows strictly faster than $g(n)$

For example, $7n+8 \in \Theta(n)$ because constants and additive terms do not change the long-run linear growth class.2

Footnotes

1. Asymptotic Notation: O(), o(), Ω(), ω(), and Θ() The Idea The Definitions - University of Arizona notes defining the standard asymptotic notations formally. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

2. What is Big O Notation Explained: Space and Time Complexity - Accessible summary of Big-O, Omega, Theta, and little-o definitions. ↩ ↩²

3. Asymptotic Analysis and Recurrences - CMU lecture covering asymptotic notation, lower bounds, and recurrence-solving methods. ↩ ↩²

4. Recurrences, Master Theorem - University of Washington lecture notes connecting asymptotic analysis with case analysis and recursive algorithms. ↩

5. Lecture 16: Introduction to Asymptotic Analysis - Cornell lecture explaining simplification, growth comparison, and why asymptotic thinking focuses on large inputs. ↩

Common growth classes and their significance

In algorithm design, the most common asymptotic classes are constant, logarithmic, linear, linearithmic, polynomial, and exponential.2 Their order from slower to faster growth is typically:

$$1 \;<\; \log n \;<\; n \;<\; n\log n \;<\; n^2 \;<\; n^3 \;<\; 2^n$$

This ranking is why binary search with $\Theta(\log n)$ is asymptotically better than linear search with $\Theta(n)$ on sorted data, and why efficient comparison sorts aim for $\Theta(n\log n)$ rather than $\Theta(n^2)$.2

Footnotes

1. Lecture 16: Introduction to Asymptotic Analysis - Cornell lecture explaining simplification, growth comparison, and why asymptotic thinking focuses on large inputs. ↩ ↩²

2. Learn Asymptotic Notation in Y Minutes - Concise overview of common growth classes and notation relationships. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸ ↩⁹

3. Asymptotic Analysis and Recurrences - CMU lecture covering asymptotic notation, lower bounds, and recurrence-solving methods. ↩ ↩² ↩³

Simplification rules used in asymptotic analysis

A central technique is asymptotic simplification: remove terms that become negligible as $n \to \infty$.2 This follows from comparing dominant growth.

Examples:2

• $3n^2 + 5n + 7 \in \Theta(n^2)$
• $n\log n + 100n \in \Theta(n\log n)$
• $4 \in \Theta(1)$
• $\log_2 n \in \Theta(\log n)$ because changing the logarithm base changes only a constant factor.

Useful rules:

1. Drop constants: $c\cdot f(n) \in \Theta(f(n))$ for constant $c>0$.
2. Keep the dominant term: if $f(n)=g(n)+h(n)$ and $g(n)$ grows faster, then $f(n)\in\Theta(g(n))$.
3. Multiply nested costs: an outer loop of $n$ iterations and inner loop of $n$ iterations yields $\Theta(n^2)$ if both run fully.
4. Sequential composition adds: if one part costs $\Theta(n)$ and another $\Theta(n^2)$, total cost is $\Theta(n^2)$.

These rules are valid only in the asymptotic sense; for small inputs, constants may still affect real performance.

Footnotes

1. Lecture 16: Introduction to Asymptotic Analysis - Cornell lecture explaining simplification, growth comparison, and why asymptotic thinking focuses on large inputs. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷

2. Learn Asymptotic Notation in Y Minutes - Concise overview of common growth classes and notation relationships. ↩ ↩²

3. Asymptotic Notation: O(), o(), Ω(), ω(), and Θ() The Idea The Definitions - University of Arizona notes defining the standard asymptotic notations formally. ↩

Best-case, average-case, and worst-case analysis

Case analysis matters when the same algorithm behaves differently on different inputs of the same size. For example, linear search may terminate immediately if the target is first, or inspect every element if the target is last or absent.

For a simple linear search over an array of size $n$:

• Best case: $\Theta(1)$
• Worst case: $\Theta(n)$
• Average case: typically $\Theta(n)$ under common assumptions about target position

This shows an important distinction:

• Asymptotic notation describes a growth relationship.
• Best/worst/average describes which input distribution or scenario is being measured.

Thus, “worst-case $\Theta(n)$” and “best-case $\Theta(1)$” are both valid statements about the same algorithm.

Footnotes

1. Recurrences, Master Theorem - University of Washington lecture notes connecting asymptotic analysis with case analysis and recursive algorithms. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

Recurrences and divide-and-conquer analysis

Many recursive algorithms are modeled by a recurrence relation of the form

$$T(n)=aT(n/b)+f(n)$$

where $a$ is the number of subproblems, $n/b$ is the subproblem size, and $f(n)$ is the non-recursive work per level.2

This form captures divide-and-conquer algorithms such as merge sort and binary search. Common tools for solving recurrences include:

• unrolling or repeated substitution
• recursion trees
• guessing and induction
• the Master Theorem2

For the classic recurrence

$$T(n)=aT(n/b)+f(n),$$

the Master Theorem compares $f(n)$ to $n^{\log_b a}$:2

1. If $f(n)=O(n^{\log_b a-\varepsilon})$ for some $\varepsilon>0$, then $$T(n)=\Theta(n^{\log_b a})$$
2. If $f(n)=\Theta(n^{\log_b a}\log^k n)$ for some $k\ge 0$, then $$T(n)=\Theta(n^{\log_b a}\log^{k+1} n)$$
3. If $f(n)=\Omega(n^{\log_b a+\varepsilon})$ for some $\varepsilon>0$ and a regularity condition holds, then $$T(n)=\Theta(f(n))$$

Example: merge sort satisfies

$$T(n)=2T(n/2)+\Theta(n)$$

Here $a=2$, $b=2$, so $n^{\log_b a}=n$. Since $f(n)=\Theta(n)$ matches that term, this is Case 2, giving

$$T(n)=\Theta(n\log n)$$

2

Footnotes

1. Asymptotic Analysis and Recurrences - CMU lecture covering asymptotic notation, lower bounds, and recurrence-solving methods. ↩ ↩² ↩³ ↩⁴ ↩⁵

2. Master Theorem: Practice Problems and Solutions - Reference summary of the Master Theorem cases and regularity condition. ↩ ↩² ↩³ ↩⁴

Worked examples

Consider several common algorithmic patterns:3

1. Single loop

   1for i = 1 to n:
   2    constant work

   Runtime: $\Theta(n)$

2. Nested loops

   1for i = 1 to n:
   2    for j = 1 to n:
   3        constant work

   Runtime: $\Theta(n^2)$

3. Halving loop

   1while n > 1:
   2    n = n/2

   Runtime: $\Theta(\log n)$ because the input shrinks by a factor of 2 each iteration.2

4. Binary search Each recursive or iterative step halves the search interval, giving $\Theta(\log n)$ worst-case runtime on sorted arrays.2

5. Linear search Runtime is $\Theta(1)$ in the best case and $\Theta(n)$ in the worst case.

A useful heuristic is to ask whether the algorithm:

• processes every element once $\rightarrow \Theta(n)$
• uses two independent passes over all pairs $\rightarrow \Theta(n^2)$
• repeatedly halves the problem $\rightarrow \Theta(\log n)$
• recursively splits into balanced subproblems plus linear merge work $\rightarrow \Theta(n\log n)$2

Footnotes

1. Recurrences, Master Theorem - University of Washington lecture notes connecting asymptotic analysis with case analysis and recursive algorithms. ↩ ↩² ↩³

2. Lecture 16: Introduction to Asymptotic Analysis - Cornell lecture explaining simplification, growth comparison, and why asymptotic thinking focuses on large inputs. ↩ ↩²

3. Asymptotic Analysis and Recurrences - CMU lecture covering asymptotic notation, lower bounds, and recurrence-solving methods. ↩ ↩² ↩³ ↩⁴

4. Learn Asymptotic Notation in Y Minutes - Concise overview of common growth classes and notation relationships. ↩

Limits, ratios, and proving asymptotic relationships

A mathematically precise way to compare functions is with ratios and limits.2 If

$$\lim_{n\to\infty}\frac{f(n)}{g(n)} = c$$

for some constant $c$ with $0<c<\infty$, then typically $f(n)\in\Theta(g(n))$.2

Examples:

• $\displaystyle \lim_{n\to\infty}\frac{7n+8}{n}=7$, so $7n+8\in\Theta(n)$.
• $\displaystyle \lim_{n\to\infty}\frac{n}{n^2}=0$, so $n\in o(n^2)$.
• $\displaystyle \lim_{n\to\infty}\frac{n^2}{n}= \infty$, so $n^2\in \omega(n)$.

This ratio perspective explains why lower-order terms vanish asymptotically: their contribution becomes negligible relative to the dominant term.2

Footnotes

1. Asymptotic Notation: O(), o(), Ω(), ω(), and Θ() The Idea The Definitions - University of Arizona notes defining the standard asymptotic notations formally. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

2. What is Big O Notation Explained: Space and Time Complexity - Accessible summary of Big-O, Omega, Theta, and little-o definitions. ↩ ↩²

3. Lecture 16: Introduction to Asymptotic Analysis - Cornell lecture explaining simplification, growth comparison, and why asymptotic thinking focuses on large inputs. ↩

Summary framework

A rigorous mental model for algorithm analysis is:

1. Model runtime or memory as a function $T(n)$.
2. If needed, separate best, average, and worst cases.
3. Simplify to its dominant asymptotic growth class.
4. Express the result with the appropriate notation: $O$, $\Omega$, or $\Theta$.2
5. For recursive algorithms, formulate and solve a recurrence, often with the Master Theorem.2

In this way, asymptotic analysis turns implementation behavior into a mathematical object that can be compared, proved, and generalized across machines and programming languages.2

Footnotes

1. Recurrences, Master Theorem - University of Washington lecture notes connecting asymptotic analysis with case analysis and recursive algorithms. ↩ ↩² ↩³

2. Lecture 16: Introduction to Asymptotic Analysis - Cornell lecture explaining simplification, growth comparison, and why asymptotic thinking focuses on large inputs. ↩

3. Asymptotic Notation: O(), o(), Ω(), ω(), and Θ() The Idea The Definitions - University of Arizona notes defining the standard asymptotic notations formally. ↩

4. What is Big O Notation Explained: Space and Time Complexity - Accessible summary of Big-O, Omega, Theta, and little-o definitions. ↩

5. Asymptotic Analysis and Recurrences - CMU lecture covering asymptotic notation, lower bounds, and recurrence-solving methods. ↩ ↩²

6. Master Theorem: Practice Problems and Solutions - Reference summary of the Master Theorem cases and regularity condition. ↩