> [!Summary] Content > *Big O*; *Big Omega*; *Big Theta*; *Little o*; *Little omega*. > > [!Definition] Definition (Big O) > Let $f,g$ be [[Real Function|functions]] on $\mathbb{R}$ such that $g$ is strictly positive. We write $f(x) \in \mathcal{O}(g(x)) \quad \text{[Big O of g(x)]}$if there exists constants $C>0$ and $x_{0} \in\mathbb{R}$ such that $\forall x > x_{0}, \quad |f(x)| \leq Cg(x) .$ > Equivalently, using [[Limit of Real Function at a Point|limits]]: $\mathcal{O}(g(x))=\left\{ f(x) : \lim_{ x \to \infty } \frac{f(x)}{g(x)} \neq \infty \right\}.$ > *Proof that definitions are equivalent*. Given $\varepsilon>0$. Then there exists $L \in\mathbb{R}, N \in \mathbb{N}$ such that $\forall x\geq N, \quad \left\lvert \frac{f(x)}{g(x)} - L \right\rvert < \varepsilon $so $|f(x)|<Cg(x)$ with $C:=L+\varepsilon$. > [!Example] > Let $f(x)=x$. Then $f \in \mathcal{O}(x^3)$. > > [!Definition] Definition (Big Omega) > We write $f(x)\in \Omega(g(x)) \quad \text{[Big Omega of g(x)]}$if there exists constants $C>0$ and $R \in \mathbb{R}$ such that $\forall x>R, \quad |f(x)|\geq Cg(x).$ > >Equivalently $\Omega(g(x))=\left\{ f(x) : \lim_{ x \to \infty } \frac{f(x)}{g(x)} \neq0 \right\}.$ > [!Definition] Definition (Big Theta) > We write $f(x)\in \Theta(g(x)) \quad \text{[Big Theta of g(x)]}$if $f\in \mathcal{O}(g)$ and $g\in \Omega(f)$. Hence there exist constants $c_{1},c_{2}>0$ and $N$ such that $\forall n >N, \quad c_{1}f(n)\leq g(n)\leq c_{2}f(n).$ > [!Definition] Definition (Little o) > We write $f(x)\in o(g(x))$ \[little o of $g(x)$\] if for every $C>0$, there exists an $R$ such that $f(x)\leq C\,g(x)$ for all $x > R$. Equivalently, $\lim_{ x \to \infty } \frac{f(x)}{g(x)} =0.$ > [!Definition] Definition (Little omega) > We write $f(x)\in \omega(g(x))$ \[little omega of $g(x)$\] if for every $C>0$, there exists an $R$ such that $f(x)\geq C\,g(x)$ for all $x > R$. Equivalently, $\lim_{ x \to \infty } \frac{f(x)}{g(x)} =\infty.$ > [!info] Intuitions > - $f(x) \in O(g(x))$ means $f \leq g$ "asymptotically". > - $f(x) \in \Omega(g(x))$ means $g \geq f$ "asymptotically". > - $f(x) \in \Theta(g(x))$ means $g = f$ "asymptotically". > - $f(x) \in o(g(x))$ means $g < f$ "asymptotically". > - $f(x) \in \omega(g(x))$ means $g > f$ "asymptotically". # Properties > [!info] Notation > - We write $f(x)=\mathcal{O}(g(x))$ to denote $f(x)\in\mathcal{O}(g(x))$. > - We write $\mathcal{O}(f(x))+\mathcal{O}(g(x))=\mathcal{O}(h(x))$ if for all $a \in \mathcal{O}(f(x))$ and $b\in \mathcal{O}{g(x)}$ we have $f(x)+g(x)\in\mathcal{O}(h(x))$. 1. If $f(x)=\mathcal{O}(g(x))$, we have $\mathcal{O}(g(x))+\mathcal{O}(f(x))=\mathcal{O}(g(x))$ 2. For any $c\in\mathbb{R}$, we have $\mathcal{O}(cf(x))=\mathcal{O}f(x)$ # Applications - [[Time complexity of an algorithm]].