---
title: "Time Complexity"
type: concept
related: [Turing Machinea, Time Complexity, Non Deterministic Computation, Regular Language, Amortized Analysis]
source: https://www.jemoka.com/posts/kbhtime_complexity/
confidence: high
status: active
---

Time complexity \(t(n): \mathbb{N} \to \mathbb{N}\), and:
\begin{equation} \text{TIME}\qty(t(n)) = \qty {\text{languages } L \mid\ \exists \text{TM that decides $L$ in $O(t(n))$ steps} } \end{equation}
notice! the Big-oh is backed into the definition. And we write:
\begin{equation} P = \bigcup_{c \in \mathbb{N}} \text{TIME}\qty(n^{c}) \end{equation}
we call this &ldquo;efficient&rdquo; vs. &ldquo;feasible&rdquo;.
\begin{equation} EXP = \bigcup_{c \in \mathbb{N}} \text{TIME}\qty(2^{n^{c}}) \end{equation}
and adding in non-determinism, we have:
\begin{equation} \text{NTIME}\qty(t(n)) = \qty {L : \exists\ \text{NTM that decides L in O(t(n)) steps}} \end{equation}
and so:
\begin{equation} NP = \bigcup_{c \in \mathbb{N}} \text{NTIME}\qty(n^{c}) \end{equation}
turing machine Time Complexity We measure a turing machine&rsquo;s time complexity via number of steps it takes for a turing machine to halt.
Let \(M\) be a turing machine that halts on all inputs; we will only consider for now decidable languages. We define:
the running time or Time Complexity of the machine \(M\) is a function \(T : \mathbb{N} \to \mathbb{N}\), such that \(T(n)\) is the maximum number of steps taken by \(M\) over all inputs of length \(n\) (the &ldquo;worst case complexity&rdquo;).
Time-Bounded Complexity Let us define:
\begin{equation} \text{TIME}\qty(t(n)) = \qty {L&rsquo; \mid \text{there&rsquo;s a TM $M$ with time complexity $O(t(n))$ so that $L&rsquo; = L(M)$}} \end{equation}
that is, \(\text{TIME}(T(n))\) a set of languages decided by some TM with \(O(t(n))\) running time.
Polynomial Time \begin{equation} P = \bigcup_{k \in N} \text{TIME}\qty(n^{k}) \end{equation}
&ldquo;efficient&rdquo;; and &ldquo;robust&rdquo;: that is, multi-tape TM theorem (number of tapes, etc.) and time hierarchy theorem
Extended Church-Turing Thesis see Extended Church-Turing Thesis
one-tape TM cannot decide some language \(A\) in less than \(O(n \log n)\) time For any
\begin{equation} f(n) = O\qty( \frac{n \log n}{\alpha \qty (n)}) \end{equation}
where \(\alpha(n)\) is unbounded, we have that \(TIME(f(n))\) contains only regular languages.
two tapes could be more powerful than one tape &hellip;because you can do things in parallel (i.e. different models of computation can yield different run times, even if they are both computable function)
in fact, something like \(B = \qty { ww \mid w \in \qty {0,1}^{*}}\) has a quadratic gap
multi-tape TM theorem Let \(t: \mathbb{N} \to \mathbb{N}\), which satisfies \(t(n) \geq n\), for all \(n\). Then, every \(t(n)\) time multi-tape TM has an equivalent \(O\qty (t(n)^{2})\) time one-tape TM.
Its transition function is:
\begin{equation} \delta : Q \times \Gamma^{k} \to Q \times \Gamma^{k-1} \times \qty {L, R, S}^{k} \end{equation}
&hellip;.because you can just append the tapes in the style of multi-tape simulation by one tape and then just move across all of \(n\) each time to increment the next tape.
correlary: suppose language \(A\) can be decided by a multi-tape Turing Machine in \(p(n)\) steps for some polynomial \(p\), then \(A\) can be decided by a one-tape TM in \(q(n)\) steps, by some polynomial \(q\) (because we just squared in the example above).
efficient universal Turing Machine there is a one-tape Turing Machine \(U\) which takes as input&hellip;.
the code of an arbitrary Turing Machine \(M\) an input string \(w\) and a string of \(t\) 1s which represents the runtime where \(t &gt; |w|\) such that \(U\qty (M,w, 1^{t})\) halts in \(O\qty (|M|^{2} t^{2})\) steps and \(U\) accepts \(\qty (M, w, 1^{t}) \Leftrightarrow M\) accepts \(w\) in \(t\) steps.
That is&hellip;. the universal Turning machine will not run forever; its a clock that goes to a certain amount of steps and gives up.
The idea to make this is to make a multi-tape TM \(U&rsquo;\) that does the above, and run the multi-tape reduction.
time hierarchy theorem &ldquo;if you get more time to compute then you can solve strictly more problems&rdquo;
254:
If \(t(n), T(n)\) are such that \(t(n) \geq n\) where \(T(n) = \omega \qty(t(n) \log\qty(t(n)))\), then \(\text{TIME}\qty(t(n)) \subset \text{TIME} \qty(T(n))\).
154:
For all reasonable (&ldquo;constructible&rdquo;) \(f,g: \mathbb{N} \to \mathbb{N}\) where for all \(n\), \(g(n) &gt; n^{2} f(n)^{2}\), then \(\text{TIME}(f(n)) \subset \text{TIME}(g(n))\) strictly contain.
proof idea: Diagonalization Arguments with a clock; make a Turing machine \(N\) on input \(M\); simulate \(M\) on input \(M\) for \(f(|M|)\) steps then flip the answer.
Proof:
let us define some machine \(N(M)\) which computes in \(t = f(|M|)\). Run \(U\qty (M, M, 1^{t})\), and output the opposite answer.
Assume for contradiction \(L(N)\) has time complexity \(f(n)\). By assumption, \(N(N)\) runs in \(f(|N|)\) time and outputs the opposite answer as \(U\qty (N, N, 1^{f\qty (|N|)})\). This is contradiction because \(N(N)\) outputting true means \(U(N, N)\) outputs false, etc. Tish is a contradiction.
This means that \(L(N)\) does not have time complexity \(f(n)\).
Recall however \(U\qty (N, N, 1^{f\qty (|N|)})\) halts in \(O\qty (|M|^{2} t^{2})\) steps, so let&rsquo;s set \(g(|M|) &gt; |M|^{2} f(|M|)^{2}\) for all \(M\).
(This also holds for multiple Turing Machines).
correlary
\begin{equation} \text{TIME}\qty(n) \subset \text{TIME}\qty(n^{2}) \subset \dots \end{equation}
there are an infinite hierarchy of increasingly time-consuming problems
example same number \begin{equation} A = \qty {0^{k} 1^{k} \mid k \geq 0} \end{equation}
for a turing machine on \(A\), on input of length \(n\), we&hellip;.
first pass: scan the tape and reject if the string is not of the form \(0^{i}1^{j}\) repeat if both $0$s and $1$s are an the tape scan across the tape, crossing off a single \(0\) and a single \(1\) if \(0\) remain after all \(1\) crossed off, then reject. otherwise, accept This has complexity of&hellip;
single scan: \(O(n)\) crossing off left right: \(O\qty (n^{2})\) verifying: \(O(n)\) actually, though, we can do this in \(O(n \log n)\) if \(w\) is not in the right shape \(0^{*}1^{*}\), reject repeat until all bits of \(w\) are crossed out if parity (odd/evenness) of \(0\) is not parity of \(1\), reject cross out every other \(0\), cross out ever other \(1\) if all bits crossed out, accept There will be \(\log n\) crossings-out at most (since each divides by \(2\)), and each of such crossings-out, will check linearly.
