The efficiency of a machine \(M\) is measured in terms of its time complexity – i.e. the number of basic steps \(time_M(x)\) required for \(M\) to halt and return an output for the input \(x\) (where the precise notion of ‘basic step’ will vary with the model \(\mathfrak{M}\)). This measure may be converted into a function of type \(\mathbb{N} \rightarrow \mathbb{N}\) by considering \(t_{M}(n) = \max \{time_M(x) : \lvert x\rvert = n \}\) – i.e. the worst case time complexity of \(M\) defined as the maximum number of basic steps required for \(M\) to halt and return an output for all inputs \(x\) of size \(n\). The worst case space complexity of \(M\) – denoted \(s_{M}(n)\) – is defined similarly – i.e. the maximum number of tape cells (or other form of memory locations) visited or written to in the course of \(M\)’s computation for all inputs of size \(n\).