[jemfinch]

Big O notation is frequently used to refer to the average case bounds of an algorithm. Haven't you seen an analysis of quicksort?