Guarda la definizione formale di Notazione Big O per vedere un limite definito all'interno della notazione lì. Mentre Big O riguarda specificamente la complessità del caso peggiore, ci sono altre notazioni per il caso medio o il caso migliore.
Di solito l'idea è di ottenere un limite superiore di quanto è cattivo l'algoritmo. La complessità è logaritmica, lineare, quadratica o esponenziale? Ci sono vari esempi che si possono dare per alcuni di questi come una ricerca binaria può avere complessità logaritmica come si sta riducendo la metà delle opzioni con ogni ricerca assumendo che il set iniziale di dati è ordinato. Quadratic potrebbe essere un cattivo algoritmo di ordinamento come Bubble Sort.
Una visione alternativa qui è di notare che "la dimensione dell'ingresso aumenta senza vincoli" è generalmente un modo di descrivere un limite come una variabile tende all'infinito. Limiti a infinito sarebbe un esempio di discussione di f (x) = 1 / x dove x cresce senza vincoli , il valore della funzione si avvicinerà a zero. La chiave è immaginare il tempo di esecuzione dell'algoritmo come una funzione in base alla dimensione dell'input e come si modifica quell'input, quanto velocemente cresce la funzione. È una linea retta o una curva? Quanto è ripida la pendenza in qualsiasi punto? Questo è il punto dietro l'idea qui.