\begin{frame}{Big O Notation} \begin{block}{} Let $f,g : {\mathbb N} \to {\mathbb R}_{>0}$. Then \begin{talign} \alert{f \in O(g)} \quad\iff\quad \exists C>0.\; \exists n_0. \; \alert{f(n) \leq C \cdot g(n)} \text{ for all } n \ge n_0 \end{talign} \end{block} \pause \begin{exampleblock}{} \begin{malign} n^a \in O(n^b) \quad&\text{ for all $00$}\\ n^a \in O(b^n) \quad&\text{ for all $a>0$ and $b>1$}\\ \log_a n \in O(n^b) \quad&\text{ for all $a,b>0$}\\ \log_a n \in O(\log_b n) \quad&\text{ for all $a,b>0$} \end{malign} \end{exampleblock} \pause\bigskip By definition $\log_a a^n=n$. \pause This implies $a^{\log_a n}=n$\pause, and hence \begin{talign} a^{\log_a b \,\cdot\, \log_b n} = \big(a^{\log_a b}\big)^{\log_b n} = b^{\log_b n} = n \end{talign} Hence \alert{$\log_a b \cdot \log_b n = \log_a n$}. \end{frame}