Algorithmic Analysis

Simulation

Surrounding a code block in a a timer

Pro	Con
Easy to interpret	Depends on the system
Easy to implement	Compiler dependent
	Not predicable for small inputs
	Relationship to input not clear

Modeling

Count the number of operations exactly

Pro	Con
Independent of system	All operations weighted equally
Input dependance is captured	Very tedious to compute
	Actual operation count varies
	Doesn’t tell you actual time

Asymptomatic Behavior

The rate that time grows as the input grows infinitely

Notation

Notation	Meaning
$O(f(n))$	Order of growth is less than or equal to f(n)
$\Theta (f(n))$	Order of growth is greater than or equal to f(n)
$\Omega (f(n))$	Order of growth is equal to f(n)
Note: This does NOT mean best, worst, and average case
Big O, Omega, Theta Notation

Types of Growth

• $O(1)$: Constant

sum += i

• $O(\log n)$: Logarithmic
  • We drop the base of the logarithm

for (int i = 1; i <= n; i *= 2) // *= base of log
	sum += i

• $O(n)$: Linear

for (int i = 0; i < n; i++)
	sum += i

• $O(n\log n)$: Linear Log
• $O(n^a)$: Polynomial
  • Number of independent nested loops = exponent

for (int i = 0; i < n; i++)
	for (int j = 0; j < n; j++)
		...
			sum += i * j * ...

• $O(a^n)$: Exponential
  • Intractable
• $O(n!)$: Factorial
  • Intractable

Tips

• Additional Independence
  • When there are two independent statements (such as loops next to each other)
  • $O(n+m)$
• Drop Constant Multipliers
  • $O(n+n)=O(2n)=O(n)$
• Drop lower order terms with similar growth rates
  • $O(n+\log n)=O(n)$
  • $O(n+\log m)$ can’t drop it because we don’t know the relationship between $n$ and $m$

Series

• If an inner loop has a dependance on the outer loop, you can’t just multiply them
  • Instead you have to use a series
• Useful series
  • $2+2^2+2^3+\cdots +2^n=\sum _{i=1}^n{2}^i=2^{n+1}-1\in O(2^n)$
  • $\frac{n}{1}+\frac{n}{2}+\frac{n}{4}+\frac{n}{8}+\cdots +0=2n-1\in O(n)$
    • For when a linear loop is dependent on a logarithmic loop it is nested in