Limite superiore asintotico

Se un’equazione di ricorrenza è espressa con un simbolo di disuguaglianza del tipo "" (o più frequentemente ""), significa che stiamo fornendo un limite superiore per il tempo di esecuzione. Questo indica che il costo dell’algoritmo non supererà mai asintoticamente il valore definito dalla ricorrenza. Di conseguenza, si utilizza la notazione Big O, che formalizza proprio questo concetto di limite superiore asintotico.

Esempio di limite superiore asintotico

Immaginiamo di analizzare un algoritmo e di poter dire che, nel peggiore dei casi, ogni passo ricorsivo impiega “al più” una certa quantità di tempo, o che la funzione di costo delle operazioni “Divide” e “Combina” è “al più” . Questo porta a una ricorrenza del tipo . Se, per esempio, tramite il metodo di sostituzione, si fa un’ipotesi per il MergeSort, questa è una dimostrazione per . Se la dimostrazione non può essere resa bidirezionale (perché magari l’analisi è volutamente più pessimistica o non completa), allora si rimane nell’ambito del limite superiore.