# Rules of Asymptotic Notation

#### Dropping the coefficient

$$
cf(n)=\Theta(f(n)) \tag{where $c$ is any positive constant}
$$

Given a function multiplied to some constant, $cf(n)$, its complexity is exactly the same as $f(n)$. This property can easily be demonstrated using the limit definition of $\Theta$.
$$
\lim_{n \to \infty}{\frac{cf(n)}{f(n)}}=\lim_{n \to \infty}{c}=c
$$

#### Higher degree polynomial

$$
f(n)^c=o(f(n)^d) \tag{for any $c<d$}
$$

Given $f(n)^c$ and $f(n)^d$ where $c$ and $d$ are constants and $c<d$, $f(n)^c$ is less complex than $f(n)^d$
$$
\begin{align*}
\lim_{n \to \infty}{\frac{f(n)^c}{f(n)^d}}&=\lim_{n \to \infty}{\frac{cf(n)^{c-1}\frac{d}{d n}f(x)}{df(n)^{d-1}\frac{d}{d n}f(x)}} \tag{for any $c<d$}\\
&=\lim_{n \to \infty}{\frac{cf(n)^{c-1}}{df(n)^{d-1}}}\\
&=\lim_{n \to \infty}{\frac{c(c-1)f(n)^{c-2}}{d(d-1)f(n)^{d-2}}}\\
&\vdots\\
&=\lim_{n \to \infty}{\frac{c(c-1)(c-2)(c-3)\cdots(c-k)}{d(d-1)(d-2)(c-3)\cdots(d-k)f(n)^{d-(k+1)}}}\\
\lim_{n \to \infty}{\frac{f(n)^c}{f(n)^d}}&=\infty
\end{align*}
$$

#### Sum of functions

$$
f(n)+g(n)=\Theta(f(n)) \tag{for any $f(n)=\Omega(g(n))$}
$$

In a sum of functions, the most complex function dominates the sum therefore the overall complexity will be equal to the dominant function. This can be shown using the set definitions.

Since $f(n) = \Omega(f(n))$,
$$
\begin{align*}
f(n)&\geq cf(n) \tag{where $n>n_0$}\\
f(n) +g(n)&\geq cf(n) \tag{since $g(n)>0$}
\end{align*}
$$
> adding $g(n)$ to the left hand side of the inequality does not change the inequalityy relationship since $g(n)$ is positive (meaning, adding $g(n)$ can only result to increasing the value of the already bigger value)

Therefore,
$$
f(n)+g(n)=\Omega(f(n))
$$
Also since $g(n)=O(f(n)),$
$$
\begin{align*}
g(n)&\leq cf(n) \\
f(n)+g(n)&\leq cf(n) + f(n)\\
f(n)+g(n)&\leq (c+1)f(n)\\
\end{align*}
$$
Therefore,
$$
f(n)+g(n)=O(f(n))
$$
And since $f(n)+g(n)=\Omega(f(n)) \land f(n) + g(n) = O(f(n))$,
$$
f(n)+g(n)=\Theta(f(n))
$$

#### Different bases on log

Bases for logarithms doesn't matter in terms of asymptotic notation therefore $\log_b{n}$ for any base is of complexity class $\Theta(\log n)$
$$
\begin{align*}
\lim_{n \to \infty} {\frac{\log_a{n}}{\log_b{n}}}&=\lim_{n \to \infty} {\frac{\frac{\log_b{n}}{\log_b{a}}}{\log_b{n}}}\\
&=\lim_{n \to \infty} {\frac{\log_b{n}}{\log_b{n}(\log_b{a})}}\\
&=\lim_{n \to \infty} {\frac{1}{\log_b{a}}}\\
\lim_{n \to \infty} {\frac{\log_a{n}}{\log_b{n}}}&=\frac{1}{\log_b{a}}
\end{align*}
$$

#### Different bases on exponential functions

$$
a^n=\omicron(b^n) \tag{for any $a<b$}
$$

Bases for exponential functions on the other hand matter, as shown in this proof:
$$
\begin{align*}
\lim_{x \to \infty}{\frac{a^n}{b^n}}&=\lim_{x \to \infty}{\frac{a^n}{(a^{\log_{a}b})^n}}\\
&=\lim_{x \to \infty}{\frac{a^n}{(a^n)^{\log_{a}b}}}\\
&=\lim_{x \to \infty}{(a^n)^{1-\log_{a}b}}\\
\end{align*}
$$
since $b>a$,$1-\log_a b<0$,
$$
\lim_{x \to \infty}{\frac{a^n}{b^n}}=0
$$