# Big O Notation **An approximate description of the limiting behaviour of a [[function]] as its argument tends to a value, typically infinity.** Big O notation is part of a [[Big O Notation#Family of Bachmann-Landau notations|larger set of notations]] known as Bachmann-Landau notation. Let $f$ be a real-valued function that is to be described and $g$ be the real-valued comparison function used in the description. Additionally, let $g(x)$ be *strictly positive* for all sufficiently large enough $x$. $f(x)$ is *big O* of $g(x)$ if the *absolute value* of $f(x)$ is at most a *positive constant multiple* of $g(x)$ for all sufficiently large enough $x$. That is, $f(x)=O(g(x))\text{ as }x\rightarrow\infty$[^1] if there exists a positive real number $M$ and real number $x_{0}$ such that $|f(x)|\le Mg(x)\text{ for all }x\ge x_{0}$ > [!Example]- > Let $f(x)=6x^{4}+2x^{3}+5$. $f(x)$ is big O of $g(x)$ if, for some real number $x_{0}$, positive real number $M$, and for all $x>x_{0}$, > $|f(x)|\le Mg(x)$ > Let $x_{0}=1$ and thus for all $x>1$, > $\begin{align} |6x^{4}+2x^{3}+5|&\le6x^{4}+2x^{4}+5x^{4} \\ &=13x^{4} \end{align}$ > As there exists both an $x_{0}$ and an $M$ that satisfies the condition, > $f(x)=O(x^{4})$ > > ![[BigONotationExample.svg|350]] > > As shown above, $13g(x)\ge f(x)$ for all $x$ past the point $x=1$. In computer science, $M$ and $x_{0}$ are replaced with *positive integers* instead for the purpose of [[time complexity]] analysis. In its most common application, big O notation is used to present an *asymptotic upper bound* and involves very large values of $x$. As such, the comparison function $g(x)$ can be derived directly from the terms of $f(x)$ which, for *large enough values* of $x$, will make all other values *negligible*. ^a4d18e - If $f(x)$ is a sum of multiple terms, it can be approximately described by the term with the largest growth rate. - If $f(x)$ is a product of multiple factors, all constants can be considered negligible. > [!Simplification example]- > From the previous example, $f(x)=f(x)=6x^{4}+2x^{3}+5$. As the $x^{4}$ term *dominates* the value of the function for very large values of $x$, > $f(x)=O(x^{4})$ > which is the same result as previously derived from the formal definition. ## Family of Bachmann-Landau notations ### Small O $f(n)=o(g(n))$ In small O notation, $f$ is *dominated* by $g$ asymptotically. $\begin{gather} \\ \forall k>0, \exists n_{0}\;\forall n>n_{0}:|f(n)|< k\;g(n) \\ \\ \lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}=0 \end{gather}$ *** ### Big O $f(n)=O(g(n))$ In big O notation, $f$ is *bounded above* by $g$ asymptotically, up to a constant. $\begin{gather} \exists k>0, \exists n_{0}\;\forall n>n_{0}:|f(n)|\le k\;g(n) \\ \\ \limsup_{n\rightarrow\infty}\frac{f(n)}{g(n)}<\infty \end{gather}$ *** ### Big Theta $f(n)=\Theta(g(n))$ In big theta notation, $f$ is *bounded above and below* by $g$ asymptotically. $\begin{gather} \exists k_{1},k_{2}>0\;\exists n_{0}\;\forall n>n_{0}:0\le k_{1}g(n)\le f(n)\le k_{2}g(n) \\ \\ f(n)=O(g(n))\text{ and }f(n)=\Omega(g(n)) \end{gather}$ *** ### Equal order $f(n)\sim g(n)$ $f$ and $g$ are equal order if they are equal asymptotically. $\begin{gather} \forall\varepsilon>0\;\exists n_{0}\;\forall n>n_{0}:\left|\frac{f(n)}{g(n)}-1\right|<\varepsilon \\ \\ \lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}=1 \end{gather}$ *** ### Big Omega - complexity theory $f(n)=\Omega(g(n))$ In big omega for complexity theory, $f$ is *bounded below* by $g$ asymptotically. $\begin{gather} \exists k>0\;\exists n_{0}\;\forall n>n_{0}:f(n)\ge k\;g(n) \\ \\ \liminf_{n\rightarrow\infty}\frac{f(n)}{g(n)}>0 \end{gather}$ *** ### Small Omega $f(n)=\omega(g(n))$ In big omega for complexity theory, $f$ *dominates* $g$ asymptotically. $\begin{gather} \exists k>0\;\exists n_{0}\;\forall n>n_{0}:f(n)> k\;g(n) \\ \\ \lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}=\infty \end{gather}$ [^1]: $f(x)=O(g(x))$ may be considered an *abuse of notation*. This expression states that $f(x)$ is big O $g(x)$, and is one of infinitely many functions that is so. It may be considered more accurate to express this as $f(x)\in O(g(x))$.