Tutorial - Algorithm and Runtime

Asymptotic Representations §

• Example: $n+log(n)$ and $n$ are asymptotically the same

Bounds §

• If function $f(x)$ is faster than $g(x)$, we may say that $f(x)$ is upper bounded (not tightly) by $g(x)$, mathematically represented as $f(n)=O(g(n))$.
  • I.e. $f(x)$ is faster than or at least equal to $g(x)$, akin to $\le$ in terms of time
• Tight Bound: both functions are equal to each other; none is faster than the other. We may then express both functions as $O(...)$ of each other
  • E.g. $n+ln(n)=O(n)$ and $N=O(n+ln(n))$
  • Then $n+ln(n)=\Omega (n)$

Mathematical Definition §

$$f(x)=O(g(x))⟺x_0,c.\forall x>x_0.f(x)\le cg(x)$$

• For some constants $a>b>1$
  • $a=\Theta (b)$
  • $lo{g}_{a}n=\Theta (lo{g}_{b}n)$
  • $n^b<O(n^a)$
  • $b^n=O(a^n)=O(n^n)$

Comparison §

• Compare each function by comparing representative elements, from slowest to fastest
  1. Exponential
  2. Polynomial
  3. Log
  4. Constant