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