  For an input, \(w\), let \(n = \lvert w\rvert\) be the length of \(w\). Following [Hartmanis, 1989] we say that a Turing machine \(M\) runs in time \(T(n)\) if for all \(w\) of length \(n, M(w)\) takes at most \(T(n)\) steps and then halts. This is called worst-case complexity because \(T(n)\) must be as large as the time taken by any input of length \(n\).