Secondo me vuol dire "dimensione dell'input" come la si intende comunemente.
Ad esempio, l'algoritmo selection sort ha complessità O(n^2) dove n è la "dimensione dell'input", ovvero la quantità di numeri (o altro) che si danno in pasto all'algoritmo affinché li ordini.

Riferito alla macchina di Turing si tratta della porzione di nastro che contiene tutto l'input da processare, ma dipende appunto dall'input, non sono... che so... sempre 5cm.