💡 For $f:\mathbb{N}⟶{\mathbb{R}}^{+}$,

$$O(f):=\{g:\mathbb{N}⟶{\mathbb{R}}^{+}|\exists C>0\forall n\in \mathbb{N}g(n)\le C\cdot f(n)\}.$$

$O(f)$ is called the order of $f$.

If a function $g$ is on the order of $f$ we write $g\in O(f)$ or equivalently $g\le O(f)$.

💡 For $f:\mathbb{N}⟶{\mathbb{R}}^{+}$,

$$\Omega (f):=\{g:\mathbb{N}⟶{\mathbb{R}}^{+}|\exists C>0\forall n\in \mathbb{N}g(n)\ge C\cdot f(n)\}.$$

We write $g\in \Omega (f)$ or $g\ge \Omega (f)$.

💡 For $f:\mathbb{N}⟶{\mathbb{R}}^{+}$,

$$\Theta (f)=O(f)\cap \Omega (f).$$

We write $g\in \Theta (f)$ or $g=\Theta (f)$.

📖 L’Hôpital’s Rules: Let $f$and $g$ be two differentiable functions. Then

$$\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}=\underset{n\to \infty }{\lim }\frac{f^{\prime }(n)}{g^{\prime }(n)}.$$

📖 Let $f:\mathbb{N}⟶{\mathbb{R}}^{+}$ and $g:\mathbb{N}⟶{\mathbb{R}}^{+}$. Then

• If $\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}=0$, then $f\le O(g)$ and $g\cancel{\le }O(f)$.
• If $\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}=C\in \mathbb{R}$, then $f\le O(g)$, $g\le O(f)$, $f=\Theta (g)$ and $g=\Theta (f)$.
• If $\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}=\infty$, then $f\cancel{\le }O(g)$, $g\le O(f)$ and $f\ge \Omega (g)$.

📖 Let $f,g,h:\mathbb{N}⟶{\mathbb{R}}^{+}$. If $f\le O(h)$ and $g\le O(h)$, then

1. For every constant $c\ge 0$, $c\cdot f\le O(h)$.
2. $f+g\le O(h)$.

💡 In general exponential runtime is regarded as bad, and polynomial runtime as good, i.e., $O(2^n)$ is bad and $O(n^4)$ for example is good.

💡 Counterintuitive facts:

• $\log n\le O(n^{0.00\dots 1})$
• $n^{10000}\le O(1.000\dots 1^n)$
• ${\log }_{2}n\le O({\log }_{3}n)$
• ${\log }_{3}n\le O({\log }_{2}n)$