\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}