La notazione Big O fornisce un limite superiore a una funzione, mentre Big Theta fornisce uno stretto legame. Tuttavia, trovo che la notazione di Big O sia tipicamente (e informalmente) insegnata e utilizzata quando in realtà significa "Big Theta".
es. "Quicksort is O (N ^ 2)" può diventare l'affermazione molto più strong "Quicksort is Θ (N ^ 2)"
Mentre l'uso di Big O è tecnicamente corretto, un uso più diffuso di Big Theta non sarebbe più espressivo e porterebbe a una minore confusione? C'è qualche ragione storica per cui questo Big O è più comunemente usato?
Wikipedia note:
Informally, especially in computer science, the Big O notation often is permitted to be somewhat abused to describe an asymptotic tight bound where using Big Theta Θ notation might be more factually appropriate in a given context.