Proof:
P = {$L$ | $L$ is a language and $L$ can be decided in $O(N^p)$ time for an input of size $N$, $p \geq 0$}
Ex) $L = \{w \# w | w \in \Sigma^* \}$
Single tape TM decider for this problem For each character, it moves $len(w) + 1$ to right and crosses things off, then it moves back Does this for each of $len(w)$ characters
N = $2len(w) + 1$
Therefore, the timing $f(N) = N (N/2)$
$f(N)$ is $O(N^2)$
But recall that we can decide $L$ in $O(N)$ time using a 2-tape turing machine. This is an example of a more general phenomenon
If a language can be decided in $T$ steps by a multitape turing machine with a constant number of tapes, then that language can be decided in $O(T^2)$ time by a single tape turing machine
Corollary: If a language $L$ can be decided in polynomial time $N^p$ by a multitape turing machine, then it can be decided in $N^{2p}$ time by a single-tape turing machine. So therefore, $L$ is in $P$ if $L$ is decided in polynomial time by a multitape turing machine
Proof: