Per classificare il tempo di calcolo (o risorse simili, come ad esempio il consumo di spazio), si è interessati a provare limiti superiori e inferiori sul tempo minimo richiesto dall' algoritmo più efficiente per risolvere un dato problema. La complessità di un algoritmo è solitamente considerata la sua complessità nel caso peggiore, a meno che non sia diversamente specificato. L' analisi di un particolare algoritmo rientra nel campo di analisi degli algoritmi. Per mostrare un T (n) superiore legato alla complessità temporale di un problema, è sufficiente mostrare che esiste un particolare algoritmo con al massimo il tempo di esecuzione T (n). Tuttavia, provare i limiti inferiori è molto più difficile, dal momento che i limiti inferiori fanno una dichiarazione su tutti gli algoritmi possibili che risolvono un dato problema. La frase "tutti gli algoritmi possibili" comprende non solo gli algoritmi oggi conosciuti, ma qualsiasi algoritmo che potrebbe essere scoperto in futuro. Per mostrare un limite inferiore di T (n) per un problema, è necessario mostrare che nessun algoritmo può avere una complessità di tempo inferiore a T (n).
Quale limite temporale è più difficile da stabilire?
limiti inferiori inferiore limiti inferiori