\begin{frame}{Big O Notation}
    Let $f,g : {\mathbb N} \to {\mathbb R}_{>0}$.
      \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
      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$}
  By definition $\log_a a^n=n$. \pause This implies $a^{\log_a n}=n$\pause, and hence
    a^{\log_a b \,\cdot\, \log_b n} = \big(a^{\log_a b}\big)^{\log_b n} = b^{\log_b n} = n
  Hence \alert{$\log_a b \cdot \log_b n = \log_a n$}.

\themex{Time Complexity: P and NP}