Notazione L

La notazione L è una notazione asintotica analoga alla notazione O-grande, denotata come per una variabile limitata tendente a infinito. Come la notazione O-grande, è usata di solito per rendere in maniera approssimativa la complessità computazionale di un particolare algoritmo. Essa è definita come dove c è una costante positiva, e è una costante . La notazione L si usa principalmente nella teoria computazionale dei numeri, per esprimere la complessità degli algoritmi per i problemi difficili della teoria dei numeri, ad es. per la fattorizzazione degli interi e per i metodi di soluzione dei logaritmi discreti. Il beneficio di questa notazione è che semplifica l'analisi di questi logaritmi. La esprime il termine dominante, e la copre tutto ciò che è minore. Quando è 0, allora è una funzione polinomiale di ln n; quando è 1, allora è una funzione completamente esponenziale di ln n (e quindi polinomiale in n). Se è compreso tra 0 e 1, la funzione è subesponenziale (e superpolinomiale).