# 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
$$