Motivation Example.
$$ \begin{aligned}&264\hspace{0.2in}\times &&112\\&528&&56\\&1056&&28\\&2122&&14\end{aligned}\\4224----7\\8448----3\\116896----1\\\begin{aligned}&&16896\\&&8448\\&&\underline{4224}\\&&29568\end{aligned} $$
The left column computed $264\times2^i$ for i from 0 to 6
The right column determined that $112_{10}=1110000_2$
From the expansion $264\times112 =(2^6+2^5+2^4)\times264$
We want a method for comparing functions (often the runtime or memory requirement for different algorithms) that ignores
We only want to compare BIG problems .
Big-O Notation to the rescue.(the $\mathcal{O}$ stands for Order) origins in 1800sā number theory, popularized in 1960sā Computer Science.
<aside> š Def.
If $f$ and $g$ are functions from the integers or real numbers ( an ordered set) to the real numbers (or a subset there of ), We say $f(x)$ is $\mathcal{O}\Big(g(x)\Big)$ if there exist constants $C$ and $k$ such that $|f(x)|\le C|g(x)|$ whenever $x>k$.
</aside>
We saw this (without context) when we were talking about nested quantifiers
i.e. $\exist C>0\ \exist k\ \forall x\Big(x>k\rarr\big|f(x)\big|\le C\big|g(x)\big|\Big)$.
Ex.
$x^2 +2x+1$ is $\mathcal{O}(x^2)$ because we could take $k=1$ and $C=4$,
we see when $x>1$:
$2x\le2x^2\hspace{0.5in}1\le x^2$
so $|x^2+2x+1|\le 4|x^2|$
$C$ and $k$ are called the witnessed.
There can be different choices of witness.
If $(C,k)$ are witnesses, then so or $(C_0+z,k_0+y)$ for any $z\ge0$ and $y\ge0$.