Changing std:sort at Google’s scale and beyond
I&#x27;m starting to question my understanding of algorithmic complexity, the author says things like &quot;complexity being worst case O(n \log n)&quot; and seems to talk about big O notation used for average cases as well.<p>I&#x27;ve learned that big O notation is always and exclusively about the worst case, for average and best cases we use Theta Θ and Omega Ω, respectively.<p>Do people not follow these definitions strictly? Has the author committed a mistake or am I missing something?<p>I did experience an interviewer once saying that my complexity analysis was wrong as the worst case would be extremely rare to hit, I did try to explain nicely that big O notation is always about the worst case, and that they were thinking about big Theta instead, now I wonder if I was wrong.