Come si scrive la complessità algoritmica? Qual è la complessità dell'ordinamento a bolle? Qual è la complessità dell'ordinamento rapido?

La complessità algoritmica viene solitamente scritta in notazione Big O, che descrive la stima asintotica del tempo di esecuzione o dell'utilizzo della memoria dell'algoritmo in funzione delle dimensioni dei dati di input.

• Bubble sort ha una complessità di O(n²) nel peggiore e nel caso medio, poiché ogni elemento viene confrontato con ogni altro.

• Quick sort funziona in media in O(n log n), ma nel caso peggiore (ad esempio, quando l'array è già ordinato e si sceglie un pessimo elemento pivot) può degradare a O(n²).

Esempio di scrittura:

Bubble sort: O(n^2)
Quick sort: O(n log n) in media, O(n^2) nel peggiore