Per misurare la difficoltà di risolvere un problema computazionale, si può desiderare di vedere quanto tempo l' algoritmo migliore richiede per risolvere il problema. Tuttavia, il tempo di funzionamento può in generale dipendere dall' istanza. In particolare, le istanze di maggiori dimensioni richiederanno più tempo per essere risolte. Così il tempo necessario per risolvere un problema (o lo spazio richiesto, o qualsiasi misura di complessità) viene calcolato in funzione della dimensione dell' istanza. Solitamente questo valore corrisponde alla dimensione dell' ingresso in bit. La teoria della complessità è interessata a come gli algoritmi scala con un aumento della dimensione in ingresso. Ad esempio, nel problema di stabilire se un grafico è collegato, quanto tempo ci vuole per risolvere un problema per un grafico con 2n vertici rispetto al tempo impiegato per un grafico con n vertici? quanto tempo richiede l' algoritmo migliore per risolvere il problema.
La teoria della complessità cerca di definire la relazione tra la scala degli algoritmi rispetto a quale altra variabile?
dimensione in ingresso dimensione in ingresso