[mantasm]

My interpretation is that "O(...)" informally means "Theta(...) in the average/amortized case". In the average case, Quicksort is Theta(n log n).