Limite asintotico stretto

Quando un’equazione di ricorrenza è espressa con un simbolo di uguaglianza, come , significa che la funzione è precisamente definita da quella relazione. Questo implica che la funzione non è né asintoticamente più veloce né più lenta della soluzione ottenuta dalla ricorrenza. Pertanto, la soluzione asintotica è un limite stretto, rappresentato dalla notazione .

Esempio di limite asintotico stretto

Consideriamo l’algoritmo Merge sort. La sua complessità è descritta dalla ricorrenza . Questa equazione descrive il comportamento esatto del tempo di esecuzione in base al modello di calcolo, considerando che la fase di divisione è in e la fase di combinazione (Merge) è in . Risolvendo questa ricorrenza (ad esempio, con il Metodo Principale o il metodo di sostituzione), si dimostra che . Questo significa che il tempo di esecuzione del Merge sort cresce esattamente come per input grandi, sia come limite superiore che inferiore.