Cosa significa T(n) in relazione a O(n)?

Quando si parla di un algoritmo, l'uso comune del simbolo [math]T[/math] è quello di rappresentare la sua complessità temporale.

[math]T[/math] è una funzione. L'input di questa funzione è la dimensione dell'input, l'output è il tempo di esecuzione (nel caso peggiore) per un input di quella dimensione.

Quindi, [math]T(n)[/math] è un numero: il numero restituito dalla funzione [math]T[/math] quando viene dato il numero [math]n[/math]. Questo numero è il tempo di esecuzione del nostro algoritmo su un input di dimensione [math]n[/math].

Il [math]O[/math] in "[math]O(n)[/math]" non è una funzione. Questa è la notazione Big O. In particolare, il simbolo [math]O(n)[/math] rappresenta la classe di tutte le funzioni che crescono (asintoticamente) al massimo alla stessa velocità della funzione lineare [math]f(n)=n[/math].

La notazione Big O ci dà un modo conveniente per parlare di limiti superiori. Per esempio, possiamo dire "la complessità temporale di questo algoritmo è [math]O(n^2)[/math]" (formalmente: "[math]T\in O(n^2)[/math]") per dire che il tempo di esecuzione dell'algoritmo è al massimo quadratico nella dimensione dell'input.

A volte, si possono vedere entrambi i simboli utilizzati in una singola equazione. Per esempio, la complessità temporale di MergeSort è comunemente descritta dalla seguente ricorrenza: "[math]T(n) = 2T(n/2) + O(n)[/math]".

Il significato di questa affermazione: Per qualsiasi [math]n[/math], il tempo [math]T(n)[/math] necessario per ordinare [math]n[/math] elementi può essere calcolato prendendo il tempo [math]T(n/2)[/math] necessario per ordinare [math]n/2[/math] elementi, moltiplicando quel tempo per 2, e aggiungendo qualcosa in più. Questo qualcosa in più deve essere al massimo lineare in [math]n[/math].