chapterTimeComplexity.tex

\chapter{Time Complexity}

\section{Basic Counts}
\rih{Double for-loops} 
$$
\sum_{i=1}^N{\sum_{j=i}^N{1}} = {N \choose 2} \sim \frac{1}{2} N^2
$$
$$
\sum_{i=1}^N{\sum_{j=i}^N{1}} \sim \int_{x=1}^N \int_{y=x}^N  \mathrm{d}y\, \mathrm{d}x
$$
\rih{Triple for-loops}
$$
\sum_{i=1}^N{\sum_{j=i}^N{\sum_{k=1}^N{1}}} = {N \choose 3} \sim \frac{1}{6} N^3
$$
$$
\sum_{i=1}^N{\sum_{j=i}^N{\sum_{k=1}^N{1}}} \sim \int_{x=1}^N \int_{y=x}^N \int_{z=y}^N \mathrm{d}z\,
\mathrm{d}y\, \mathrm{d}x
$$

\section{Solving Recurrence Equations}
Basic recurrence equation solving techniques:
\begin{enumerate}
\item Guessing and validation
\item Telescoping
\item Recursion tree
\item Master Theorem
\end{enumerate}

\subsection{Master Theorem}
Recurrence relations:
$$T(n) = a \; T\!\left(\frac{n}{b}\right) + f(n)\mbox{, where }a \geq 1 \mbox{, } b > 1$$

Notice that $b>1$ rather than $b\geq1$.

\subsubsection*{Case 1, dominated by the 1st term}
If:
$$f(n) = o(n^{\log_b a})$$

, where in the condition it is $o$ rather than $O$. \\\\
Then:
$$T(n) = \Theta(n^{\log_b a})$$
\subsubsection*{Case 2, non-dominance}
If:
$$f(n) = \Theta(n^{\log_b a} \log^{k} n)$$

, for some constant $k \geq 0$\\\\
Then:
$$
T(n) = \Theta(n^{\log_b a} \log^{k+1} n)
$$

, typically $k=0$ in most cases. 
\subsubsection*{Case 3, dominated by the 2nd term}
If:
$$f(n) = \omega(n^{\log_b a})$$

, where in the condition it is $\omega$ rather than $\Omega$. \\\\
And with regularity condition:
$$f(\frac{n}{b}) \le k f(n)$$

, for some constant $k < 1$ and sufficiently large $n$\\\\
Then:
$$T\left(n \right) = \Theta\left(f(n) \right)$$
\section{Useful Math Equations}
\runinhead{Euler.}
$$
\frac{1}{2}+\frac{1}{3}+\frac{1}{4} + ... + \frac{1}{n} = \ln{n}
$$
\runinhead{Logarithm power.}
$$
a^{\log_b^n} = n^{\log_b^a}
$$

Proof:
\begin{align*}
a^{\log_b^n} &= n^{\log_b^a} \\
\Leftarrow \ln{a^{\log_b^n}} &= \ln{n^{\log_b^a}}\\
\Leftarrow  \frac{\ln n}{\ln b}\ln a &=\frac{\ln a}{\ln b}\ln n
\end{align*}

\runinhead{Discrete to continuous.}

if $f(x)$ is monotonously decreasing, then
$$
\int_1^{+\infty}f(x) \diff x \leq \sum_{i=1}^{+\infty} f(i) \leq f(1) + \int_1^{+\infty}f(x) \diff x 
$$