Originariamente inviato da Alhazred
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.
La complessità che intendi tu credo che sia la complessità in tempo e viene calcolata per un "n" che tende a più infinito. Anche se anche qui effettivmente per quanto grando può essere "n" deve comunque avere un unità di misura.

Per la complessità in tempo si conta se ci sono array allora è n*grandezza del tipo dell'array e cose cosi. E ad ogni modo serve un qualche tipo di unità di misura.

Però appunto non riesco a capire che senso ha fare un riferimento alla macchina di turing.

Conta che nella pagine successive delle slide da un modello di costo in cui dice che ogni variabile di tipo elementare ha costo unitario, gli array invece hanno un costo pari ad n*costo del singolo elemento (quindi se è un array di interi è n*1). Il punto è che il costo è unitario, ma qual'è l'unita di misura? che centra la macchina di turing? mbho!