Algorithm Design

An algorithm is efficient if its running time is a polynomial in the input size $T$
- The running time is upper bounded by $c . T^{d}$ for some constants $c, d > 0$
- ex: brute force can solve Gale Shapley Algorithm in $n!$
2 main complexities:
- Time Complexity
- Space Complexity

To measure a Efficient Algorithm
$f (n)$ is asymptotically bounded by $g (n)$
- if $g (n)$ is asymptotically upper bound: Big O Notation
- if $g (n)$ is asymptotically lower bound: Big Omega Notation
- if $g (n)$ is asymptotically tight bound: Big Theta Notation
Propositions:
1. if $n \to \infty lim \frac{f ( n )}{g ( n )} = c$ for some constant $c > 0$ then $f (n) = Θ (g (n))$
  - Proof: $c - ϵ \leq \frac{f ( n )}{g ( n )} \leq c + ϵ$ by definition
  - $(c - ϵ) g (n) \leq f (n) \leq (c + ϵ) g (n)$
  - by definition of Big Theta notation, it is true
2. if $n \to \infty lim \frac{f ( n )}{g ( n )} = 0$ then $f (n) = O (g (n))$
3. if $n \to \infty lim \frac{f ( n )}{g ( n )} = \infty$ then $f (n) = Ω (g (n))$
To find which notation a function belongs to, do $\frac{f ( n )}{g ( n )}$

Polynomials:
- $f (n) = \sum_{k = 0}^{d} a_{k} n^{k} = O (n^{d}), a_{d} > 0$
- as $n \to \infty lim \frac{f ( n )}{n ^{d}} = a_{d} > 0$
Logarithms:
- $lo g_{a} (n) = Θ (lo g_{b} n)$ for every $a > 1$ and $b > 1$
- as $n \to \infty lim \frac{lo g _{a} n}{lo g _{b} n} = \frac{1}{lo g _{b} a} = c$
Logarithms and Polynomials:
- $lo g_{a} n = O (n^{d})$ for every $a > 1$ and every $d > 0$
- as $n \to \infty lim \frac{lo g _{a} n}{n ^{d}} = 0$
Exponentials:
- $n^{d} = O (r^{n})$ for every $r > 1$ and every $d > 0$
- as $n \to \infty lim \frac{n ^{d}}{r ^{n}} = 0$
Factorials:
- $n! = 2^{Θ (n l o g n)}$
- as by Stirling’s Fomula $n! \approx 2 πn (\frac{r}{e})^{n}$

StrixTheKiet Notes