9/110
\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}