Big O Notation è una notazione matematica utilizzata per descrivere la complessità di un algoritmo o di una funzione calcolabile. In informatica viene utilizzato per misurare l'efficienza di un algoritmo, ovvero la quantità di tempo e/o spazio utilizzata dalla sua implementazione.
La notazione Big O è uno strumento per misurare la complessità degli algoritmi, spesso calcolando gli scenari peggiori o migliori, motivo per cui a volte viene chiamata "Big O" (o Big Order). La notazione Big O, tuttavia, non misura accuratamente alcuna particolare misura di complessità, ma piuttosto è uno strumento per approssimare la complessità.
La notazione Big O fornisce una misurazione della complessità temporale nel caso peggiore e fornisce un'indicazione generale di quanto ci si può aspettare che l'algoritmo funzioni in termini di tempo e spazio. Utilizzando la notazione Big O, è possibile determinare la complessità temporale di un determinato algoritmo, che fornisce un'indicazione su come viene eseguito l'algoritmo al crescere della dimensione dell'input.
La notazione Big O è espressa come O(f(n)), dove f(n) è la complessità temporale di un algoritmo. Le complessità temporali comuni espresse con la notazione Big O includono O(1) per complessità temporale costante, O(log n) per complessità temporale logaritmica, O(n) per complessità temporale lineare, O(n2) per complessità temporale quadratica e O (2n) per complessità temporale esponenziale.
La notazione Big O può essere utilizzata per confrontare diversi algoritmi, consentendo l'identificazione dell'algoritmo più efficiente per un dato problema. Utilizzando la notazione Big O, è possibile determinare gli algoritmi più adatti a risolvere determinati problemi tenendo conto delle risorse e del tempo.
