Measuring Algorithm Efficiency with Asymptotic Notation

Purpose

Running time is roughly proportional to the number of simple operations performed, so counting operations as a function of input size is how we compare algorithms without benchmarking them. This note pins down the three asymptotic notations and the growth-rate facts worth memorizing.

O-Notation

Given two functions $f(n)$ and $g(n)$, we say that $f(n)$ is $O(g(n))$ if there exist constants $c$ and $n_0$ such that $0\le f(n)\le c\cdot g(n)$ for all $n\ge n_0$.

Omega-Notation

Given two functions $f(n)$ and $g(n)$, we say that $f(n)$ is $\Omega (g(n))$ if there exist constants $c$ and $n_0$ such that $0\le c\cdot g(n)\le f(n)$ for all $n\ge n_0$.

Theta-Notation

Given two functions $f(n)$ and $g(n)$, we say that $f(n)$ is $\Theta (g(n))$ if there exist constants $c_1$, $c_2$, and $n_0$ such that $0\le c_1\cdot g(n)\le f(n)\le c_2\cdot g(n)$ for all $n\ge n_0$.

The three bounds

Notation	Role	Guarantee for all $n\ge n_0$
$O(g)$	upper bound	$f(n)\le c\cdot g(n)$
$\Omega (g)$	lower bound	$f(n)\ge c\cdot g(n)$
$\Theta (g)$	tight bound	both, with separate constants

Common Bounds

Logarithms grow slower than every polynomial $n^{ϵ}$ with $ϵ>0$, and every polynomial grows slower than every exponential $b^n$ with $b>1$.

Polynomial

Logarithmic

Base changes only shift a logarithm by a constant factor, since ${\log }_{a}n=\frac{{\log }_{b}n}{{\log }_{b}a}$.

Exponential

Factorial

”Efficient” Algorithms

A single CPU core executes on the order of $10^9$ simple operations per second. That budget makes exponential algorithms useless beyond tiny inputs: $2^{60}$ operations is decades of compute, and $n!$ blows past that at $n=20$.

Polynomial time is the standard bar for an efficient algorithm, and it has a useful scaling property: if the input size grows by a constant factor, the running time of a polynomial time algorithm also grows by a constant factor.

Related notes

• divide and conquer
• dynamic programming
• interval scheduling