7. Algorithm Analysis

7.1 O notation

Big O notation: a mathematical way of describing how a function generally behaves in relation to the input size

Rules:
Highest order term kept
Constants omitted

Composite function	Big O notation
$c\cdot O(f(x))$	$O(f(x))$
$c+O(f(x))$	$O(f(x))$
$g(x)\cdot O(f(x))$	$O(g(x)\cdot f(x))$
$g(x)+O(f(x))$	$O(g(x)+f(x))$

Notation	Name
$O(1)$	Constant
$O(\log N)$	Logarithmic
$O(N)$	Linear
$O(N\log N)$	Log-linear
$O(N^2)$	Quadratic
$O(c^N)$	Exponential

7.2 Constant time operations

Constant time operation: an operation that always operates in the same amount of time for a given processor regardless of input values

Common constant time operations:

• Addition, subtraction, multiplication, and division of fixed size integer or floating point values
• Assignment of a reference, pointer, or other fixed size data value
• Comparison of two fixed size data values
• Read or write an array element at a particular index

Both hardware and programming language affect whether an operation is constant time

7.3 Algorithm analysis

Worst-case runtime: the runtime complexity for an input that results in the longest execution

int sum = 0;
for (int i = 0; i < N; i++) {
    sum += i;
}

Stage	Operations	Count
Before loop	sum = 0, i = 0	2
Within loop	i < N, i++, sum += i	3N
After loop	Final comparison i < N	1
Total		3 + 3N

$f(N)=2+3N+1$
$O(2+3N+1)=O(3+3N)=O(N)$
Operations before and after the loop execute a constant number of times, while operations within the loop execute N times

7.4 Growth of functions and complexity

Notation	Meaning
$T(N)$	Runtime function
$f(N)$	Comparison function
$N$	Input size
$N_0$	Threshold for asymptotic bounds

Lower bound: a function $f(N)$ that is $\le$ the best case $T(N)$, for all values of $N\ge N_0$
Upper bound: a function $f(N)$ that is $\ge$ the best case $T(N)$, for all values of $N\ge N_0$

An algorithm has infinitely many valid bounds, but we prefer the tightest asymptotic bounds that best describe its growth rate

Commonly used criteria used to choose a preferred upper or lower bound:

• A single-term polynomial
• Bounds $T(N)$ as tightly as possible
  An algorithm has infinitely many bounds. Preferred bounds are single-term polynomials that are as tight as possible and hold for all $N\ge 1$.

Ex.,

• Best case (lower bound): $3N+6\ge 3N$, for all $N\ge 1$.
• Worst case (upper bound): $5N^2+7N\le 12N^2$, for all $N\ge 1$.

Asympottic notation: the classification of runtime complexity that uses functions that indicate only the growth rate of the bounding function

Notation	Bound	General form	Meaning
$O$ (big O notation)	Upper bound	$T(N)=O(f(N))$	A positive constant $c$ exists such that, for all $N\ge N_0$, $T(N)\le c\cdot f(N)$.
$\Omega$ (big Omega notation)	Lower bound	$T(N)=\Omega (f(N))$	A positive constant $c$ exists such that, for all $N\ge N_0$, $T(N)\ge c\cdot f(N)$.
$\Theta$ (big Theta notation)	Upper and lower bound	$T(N)=\Theta (f(N))$	$T(N)=O(f(N))$ and $T(N)=\Omega (f(N))$.
If no valid constants $c$ and threshold exist, the Big-O, Big-Ω, or Big-Θ claim is false.