Asymptotic Notation: short notes (Algorithms)

Introduction

The exact running time of a program depends on the machine, the compiler and the input. To compare algorithms rather than programs, we describe how the running time grows as the input size $n$ grows, ignoring constant factors and small inputs. Asymptotic notation is the language for this: it lets us say that merge sort takes " $\Theta(n \lg n)$ time in the worst case" and mean something precise.

There are five notations: $O$ , $\Omega$ , $\Theta$ , $o$ and $\omega$ . Each is a statement about two functions for all sufficiently large $n$ . They are used for running time, space, number of comparisons, or any other cost measure, and in any case (worst, best or average).

Throughout, $\lg n$ means $\log_2 n$ , and functions are asymptotically non-negative (non-negative for all large $n$ ), as running times are.

Prerequisites

Limits: limits at infinity and L'Hopital's rule, used in the limit test.
Laws of logarithms and exponents: $a^{\log_b c} = c^{\log_b a}$ , $\log_b n = \lg n / \lg b$ .

Core concepts

The five definitions

Let $f$ and $g$ be functions from the positive integers to the reals. Each notation defines a set of functions, so " $f(n) = O(g(n))$ " really means $f(n) \in O(g(n))$ . The definitions below are those of CLRS 3e, Section 3.1.

Notation	Definition	Informal reading
$f(n) = O(g(n))$	there exist constants $c > 0$ and $n_0 > 0$ with $0 \le f(n) \le c\,g(n)$ for all $n \ge n_0$	$f$ grows no faster than $g$ (upper bound)
$f(n) = \Omega(g(n))$	there exist constants $c > 0$ and $n_0 > 0$ with $0 \le c\,g(n) \le f(n)$ for all $n \ge n_0$	$f$ grows at least as fast as $g$ (lower bound)
$f(n) = \Theta(g(n))$	there exist constants $c_1, c_2 > 0$ and $n_0 > 0$ with $0 \le c_1 g(n) \le f(n) \le c_2 g(n)$ for all $n \ge n_0$	$f$ grows at the same rate as $g$ (tight bound)
$f(n) = o(g(n))$	for every constant $c > 0$ there is an $n_0 > 0$ with $0 \le f(n) < c\,g(n)$ for all $n \ge n_0$	$f$ grows strictly slower than $g$
$f(n) = \omega(g(n))$	for every constant $c > 0$ there is an $n_0 > 0$ with $0 \le c\,g(n) < f(n)$ for all $n \ge n_0$	$f$ grows strictly faster than $g$

The difference between $O$ and $o$ is the quantifier on $c$ . For $O$ it is enough that some constant works; for $o$ every positive constant must work, however small. So $2n^2 = O(n^2)$ but $2n^2 \ne o(n^2)$ , while $2n = o(n^2)$ .

Theorem (CLRS 3e, Theorem 3.1). $f(n) = \Theta(g(n))$ if and only if $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$ .

Graphical meaning of Theta, O and Omega — Figure 1. Three panels. Theta: beyond $n_0$ , $f(n)$ stays between $c_1 g(n)$ and $c_2 g(n)$ . O: beyond $n_0$ , $f(n)$ stays on or below $c\,g(n)$ . Omega: beyond $n_0$ , $f(n)$ stays on or above $c\,g(n)$ . The behaviour to the left of $n_0$ does not matter.

Analogy with comparing numbers

Functions	Numbers
$f = O(g)$	$a \le b$
$f = \Omega(g)$	$a \ge b$
$f = \Theta(g)$	$a = b$
$f = o(g)$	$a < b$
$f = \omega(g)$	$a > b$

The analogy breaks in one place: trichotomy fails. For real numbers exactly one of $a < b$ , $a = b$ , $a > b$ holds. Two functions can be incomparable. Take $g(n) = n^2$ and

f(n) = \begin{cases} n & n \text{ even} \\ n^3 & n \text{ odd.} \end{cases}

On even $n$ , $f(n)/g(n) = 1/n \to 0$ , so $f \ne \Omega(g)$ . On odd $n$ , $f(n)/g(n) = n \to \infty$ , so $f \ne O(g)$ . Neither bound holds.

Properties

For asymptotically positive $f$ , $g$ , $h$ :

Transitivity (all five): $f = O(g)$ and $g = O(h)$ imply $f = O(h)$ ; likewise for $\Omega$ , $\Theta$ , $o$ , $\omega$ .
Reflexivity: $f = O(f)$ , $f = \Omega(f)$ , $f = \Theta(f)$ . Never $f = o(f)$ or $f = \omega(f)$ .
Symmetry: $f = \Theta(g)$ if and only if $g = \Theta(f)$ .
Transpose symmetry: $f = O(g) \iff g = \Omega(f)$ , and $f = o(g) \iff g = \omega(f)$ .
Strictness: $o(g) \subset O(g)$ and $o(g) \cap \Omega(g) = \emptyset$ ; similarly $\omega(g) \subset \Omega(g)$ and $\omega(g) \cap O(g) = \emptyset$ .
Sum rule: $f(n) + g(n) = \Theta(\max(f(n), g(n)))$ , because $\max \le f + g \le 2 \max$ . So lower-order terms can be dropped: $3n^2 + 10n + 5 = \Theta(n^2)$ .
Product rule: $O(f) \cdot O(g) = O(f g)$ ; the same holds for $\Omega$ and $\Theta$ .
Constant factors: $c\,f = \Theta(f)$ for any constant $c > 0$ .

The limit test

If $g(n) > 0$ for large $n$ and the limit $L = \lim_{n \to \infty} f(n)/g(n)$ exists (allowing $L = \infty$ ), then:

Value of $L$	Conclusion
$L = 0$	$f = o(g)$ , hence also $f = O(g)$
$0 < L < \infty$	$f = \Theta(g)$
$L = \infty$	$f = \omega(g)$ , hence also $f = \Omega(g)$

For $o$ and $\omega$ the test is also necessary: $f = o(g)$ exactly when the limit is 0. For $\Theta$ it is only sufficient: $f(n) = n(2 + \sin n)$ is $\Theta(n)$ (it lies between $n$ and $3n$ ), yet $f(n)/n$ has no limit. When the limit does not exist, go back to the definitions.

Standard growth rates

For constants $k>2$ , $0<\varepsilon<1$ and $a>1$ , each function below is $o$ of the next:

1 \;\prec\; \lg \lg n \;\prec\; \lg n \;\prec\; (\lg n)^k \;\prec\; n^{\varepsilon} \;\prec\; n \;\prec\; n \lg n \;\prec\; n^2 \;\prec\; n^k\ (k > 2) \;\prec\; a^n \;\prec\; n! \;\prec\; n^n,

where $\prec$ means "is little-o of". The three facts doing the work are:

Polylogarithms lose to polynomials. $(\lg n)^k = o(n^{\varepsilon})$ for every $k > 0$ , $\varepsilon > 0$ , however large $k$ and small $\varepsilon$ .
Polynomials lose to exponentials. $n^k = o(a^n)$ for every $k > 0$ and $a > 1$ .
Exponentials with different bases differ. For $1 < a < b$ , $a^n = o(b^n)$ . So $2^n = o(3^n)$ and $2^n = o(4^n)$ .

Useful identities and estimates:

Base of a logarithm does not matter. $\log_b n = \lg n / \lg b = \Theta(\lg n)$ for any constant $b > 1$ . That is why we write $O(\lg n)$ without a base. The base of an exponential does matter.
Exponent of a logarithm. $\lg(n^k) = k \lg n = \Theta(\lg n)$ , but $(\lg n)^k$ is a different, larger class for $k > 1$ .
Swapping base and argument. $a^{\log_b c} = c^{\log_b a}$ . For example $2^{\lg n} = n$ , $4^{\lg n} = n^2$ and $n^{\lg 3} = 3^{\lg n}$ .
Factorials (Stirling). $n! = \sqrt{2\pi n}\,(n/e)^n (1 + \Theta(1/n))$ . Consequences: $\lg(n!) = \Theta(n \lg n)$ , $n! = o(n^n)$ and $n! = \omega(2^n)$ .
Shifts. $(n + a)^b = \Theta(n^b)$ for constants $a$ and $b > 0$ ; $2^{n+1} = 2 \cdot 2^n = \Theta(2^n)$ ; but $2^{2n} = 4^n \ne O(2^n)$ .

Growth-rate comparison of common functions — Figure 2. Growth of $\lg n$ , $\sqrt{n}$ , $n$ , $n \lg n$ , $n^2$ and $2^n$ for $1 \le n \le 20$ , with the points where $n^2 = 2^n$ ( $n = 2$ and $n = 4$ ) marked; $2^n > n^2$ for every $n \ge 5$ .

Worked examples

Example 1: proving a Theta bound with explicit constants

Claim: $f(n) = 3n^2 + 10n + 5 = \Theta(n^2)$ .

Lower bound. $3n^2 \le 3n^2 + 10n + 5$ for all $n \ge 1$ . Take $c_1 = 3$ .
Upper bound. Try $c_2 = 4$ : we need $3n^2 + 10n + 5 \le 4n^2$ , that is $n^2 - 10n - 5 \ge 0$ . The positive root is $5 + \sqrt{30} \approx 10.48$ , so the inequality holds for every integer $n \ge 11$ and fails at $n = 10$ ( $-5 < 0$ ).

So $c_1 = 3$ , $c_2 = 4$ , $n_0 = 11$ witness the bound. Other choices work too: $c_2 = 18$ works from $n_0 = 1$ , since $3n^2 + 10n + 5 \le 3n^2 + 10n^2 + 5n^2$ for $n \ge 1$ . The constants are not unique; only their existence matters.

Example 2: showing a bound fails

Claim: $n^3 \ne O(n^2)$ . Suppose $n^3 \le c\,n^2$ for all $n \ge n_0$ . Dividing by $n^2$ gives $n \le c$ for all $n \ge n_0$ , which is false for $n > \max(c, n_0)$ . The same argument shows $2^{2n} \ne O(2^n)$ : it would need $2^n \le c$ for all large $n$ .

Example 3: ranking functions

Arrange in increasing order of growth: $2^n$ , $n \lg n$ , $n^{\lg n}$ , $(\lg n)^{10}$ , $n!$ , $\sqrt{n}$ , $4^n$ , $\lg(n!)$ , $n^{1.01}$ .

Rewriting each function, or taking its $\lg$ , is a quick way to compare those that grow faster than any polynomial:

Function	Rewrite or logarithm	Class
$(\lg n)^{10}$	$10 \lg \lg n$	polylogarithmic
$\sqrt{n}$	$\tfrac{1}{2} \lg n$	polynomial, degree $1/2$
$n \lg n$ and $\lg(n!)$	$\lg(n!) = \Theta(n \lg n)$ by Stirling	$\Theta(n \lg n)$ (same class)
$n^{1.01}$	$1.01 \lg n$	polynomial, degree $1.01$
$n^{\lg n}$	$(\lg n)^2$	quasi-polynomial
$2^n$	$n$	exponential
$4^n$	$2n$	exponential, larger base
$n!$	$\lg(n!) = \Theta(n \lg n)$	factorial

Answer: $(\lg n)^{10} \prec \sqrt{n} \prec n \lg n \asymp \lg(n!) \prec n^{1.01} \prec n^{\lg n} \prec 2^n \prec 4^n \prec n!$ , where $\asymp$ means $\Theta$ of each other.

Two cautions about the log trick:

If $\lg f = o(\lg g)$ and $\lg g \to \infty$ , then $f = o(g)$ . This settles $n^{\lg n}$ versus $2^n$ : $(\lg n)^2 = o(n)$ .
If only $\lg f = \Theta(\lg g)$ , nothing follows: $\lg(n^2) = 2\lg n = \Theta(\lg n)$ , yet $n^2 \ne O(n)$ . Similarly $\lg(2^n) = n$ and $\lg(4^n) = 2n$ are $\Theta$ of each other, but $4^n = \omega(2^n)$ . Compare the functions themselves in such cases.

Note also that $n^{1.01}$ beats $n \lg n$ only for very large $n$ : at $n = 2^{20}$ , $n^{0.01} = 2^{0.2} \approx 1.15$ while $\lg n = 20$ . Asymptotic order says nothing about where the crossover occurs.

Example 4: disguised functions

Several functions look exotic but become simple once written as a power of 2. Put $n = 2^m$ , so $m = \lg n$ :

Function	As a power of 2	Class
$n^{1/\lg n}$	$2^{1}$	$\Theta(1)$ , the constant 2
$(\sqrt{2})^{\lg n}$	$2^{m/2}$	$\sqrt{n}$
$2^{\sqrt{\lg n}}$	$2^{\sqrt{m}}$	faster than every polylog, slower than every $n^{\varepsilon}$
$(\lg n)^{\lg n}$	$2^{m \lg m}$	equal to $n^{\lg \lg n}$ : superpolynomial, subexponential
$n^{\lg 7}$	$2^{m \lg 7}$	$n^{2.807\ldots}$ , so $o(n^{2.81})$ but $\omega(n^{2.8})$

The third row is the one to watch. Against a polylog $(\lg n)^k = 2^{k \lg m}$ , the exponent $\sqrt{m}$ beats $k \lg m$ ; against $n^{\varepsilon} = 2^{\varepsilon m}$ , the exponent $\varepsilon m$ beats $\sqrt{m}$ . Since the exponent differences tend to infinity, the log trick applies in both directions. Crossovers can be far out: $\sqrt{m} > 10 \lg m$ fails for every integer $m$ from 2 to 20,519 and holds from $m = 20{,}520$ on, so $2^{\sqrt{\lg n}}$ overtakes $(\lg n)^{10}$ only beyond $n = 2^{20520}$ .

The last row matters for Strassen's $\Theta(n^{\lg 7})$ : $\lg 7 \approx 2.8074$ , so " $O(n^{2.81})$ " is a correct upper bound and " $O(n^{2.8})$ " is false.

Notation versus cases

Asymptotic notation and the case of analysis are independent choices.

The case fixes a function: the worst-case running time $T_{\text{worst}}(n)$ is the maximum over inputs of size $n$ ; the best case is the minimum; the average case is an expectation under a stated input distribution.
The notation then bounds that function.

So "the worst case of insertion sort is $\Theta(n^2)$ " and "the best case of insertion sort is $\Theta(n)$ " are both precise. "The running time of insertion sort", with no case, is not a single function; the strongest correct statements about it are $O(n^2)$ and $\Omega(n)$ . It is not $\Theta(n^2)$ on every input.

Common misreadings to avoid:

" $O$ means worst case and $\Omega$ means best case." False. A worst case can have a lower bound (the worst case of merge sort is $\Omega(n \lg n)$ ), and a best case can have an upper bound.
" $O(n^2)$ means the algorithm takes about $n^2$ steps." False. $O$ is only an upper bound; a $\Theta(n)$ algorithm is also $O(n^2)$ . Use $\Theta$ when the bound is tight.
In an equation such as $T(n) = 2n^2 + \Theta(n)$ , the $\Theta(n)$ stands for some anonymous function in that set.

Important properties and observations

$f = O(g)$ does not imply $2^{f} = O(2^{g})$ . Counterexample: $f(n) = 2n$ , $g(n) = n$ ; then $2^{2n} = 4^n \ne O(2^n)$ .
$f = O(g)$ does not imply $g = O(f)$ : $n = O(n^2)$ but $n^2 \ne O(n)$ .
$f(n) = O(f(n)^2)$ fails when $f(n) \to 0$ , for example $f(n) = 1/n$ . It holds when $f(n) \ge 1$ for large $n$ .
$f(n) = \Theta(f(n/2))$ holds for polynomials ( $n^2$ versus $n^2/4$ ) but fails for $2^n$ , since $2^n / 2^{n/2} = 2^{n/2} \to \infty$ .
$f(n) + o(f(n)) = \Theta(f(n))$ .
Asymptotic order is about large $n$ only. An algorithm with cost $100 n$ is $o(n^2)$ yet slower than one with cost $n^2$ for every $n < 100$ .
For polynomials: $a_d n^d + \dots + a_0 = \Theta(n^d)$ when $a_d > 0$ .

GATE examination perspective

True/false statements on pairs of functions. For each pair, decide which of $O$ , $\Omega$ , $\Theta$ , $o$ , $\omega$ hold, using the limit test where the limit exists and the definitions otherwise.
Ranking functions by growth rate. Rewrite each function as a power of 2 or of $n$ , compare logarithms with the cautions above, and remember $\lg(n!) = \Theta(n \lg n)$ and $a^{\log_b c} = c^{\log_b a}$ .
Traps. Bases of exponentials matter ( $2^n$ versus $4^n$ ); bases of logarithms do not. $\lg(n^k)$ is $\Theta(\lg n)$ but $(\lg n)^k$ is not $\Theta(\lg n)$ for fixed $k>0$ , $k\ne1$ . $n^{\lg n}$ is superpolynomial but subexponential. A function can be in neither $O(g)$ nor $\Omega(g)$ . $2^{\sqrt{\lg n}}$ lies strictly between polylogarithmic and polynomial.
Disguised constants and powers. $n^{1/\lg n} = 2$ ; $(\lg n)^{\lg n} = n^{\lg \lg n}$ ; $4^{\lg n} = n^2$ . Convert to a power of 2 before comparing.
Precision of language. A statement can turn on $O$ versus $\Theta$ and on which case (worst or best) is meant. Read both.

Summary

Time and Space Complexity Analysis: dependent. Applies these notations to loops and memory.
Solving Recurrences and the Master Theorem: dependent. Asymptotic solutions of recursive running times.
Searching: Linear and Binary Search: dependent. $\Theta(n)$ versus $\Theta(\lg n)$ in practice.
Hashing and Hash Functions: dependent. Expected-case $O(1)$ bounds.
Greedy Algorithms: related. Running-time statements for greedy methods.

Asymptotic Notation

Introduction

Prerequisites

Core concepts

The five definitions

Analogy with comparing numbers

Properties

The limit test

Standard growth rates

Worked examples

Example 1: proving a Theta bound with explicit constants

Example 2: showing a bound fails

Example 3: ranking functions

Example 4: disguised functions

Notation versus cases

Important properties and observations

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

Core concepts

The five definitions

Analogy with comparing numbers

Properties

The limit test

Standard growth rates

Worked examples

Example 1: proving a Theta bound with explicit constants

Example 2: showing a bound fails

Example 3: ranking functions

Example 4: disguised functions

Notation versus cases

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps