\begin{frame}{Time Complexity}
  Let $f,g : \mathbb{N} \to \mathbb{N}$.

  \begin{block}{}
    A nondeterministic Turing machine $M$ 
    \begin{center}
      \emph{runs in time} $f$
    \end{center}
    if for \alert{every input} $w$, \alert{every computation} of $M$ 
    reaches a halting state after \alert{at most $f(|w|)$ steps}. 
  \end{block}
  \pause\medskip
  
  \begin{goal}{}
    The function $f$ gives an upper bound on the number of computation steps
    in terms of the length of the input word.
  \end{goal}
  \pause\medskip

  \begin{block}{}
    A Turing machine $M$ has 
    \begin{center}
      \emph{time complexity} $O(g)$
    \end{center}
    if there exists $f \in O(g)$ such that $M$ runs in time $f$. 
  \end{block}
\end{frame}