[robconery]

OP here. Big O is indeed "worst case scenario" always, the size of the data set doesn't matter. An O(n) operation doesn't care if the data is sorted - even if it's the first item as you suggest. When you discuss Big O it's always worst case.

[kadoban]

If Big O is always worst case, you're going to have a hard time saying anything interesting or useful about quicksort, for instance, or hash tables.

You're going to be limited to "quicksort is O(n^2)" and "hash table lookup is O(n)", both of which are quite misleading.

There are good reasons that we usually look at the worst case, but big-O does not fundamentally or necessarily mean that.

[roel_v]

Well that's not what your article is saying - it says (well, not in these words, but it's at least what I got from it) that it's meant to be something practical to understanding algorithmic complexity and how that relates to code performance. And for that, the size of the data and the details of the algorithm very much do matter. Throughout these comments, people seem to be using two 'concepts' of big O and because of that, talking past each other: the academic 'provable upper boundary' concept and the applied 'what algorithm or data structure should I choose for my concrete problem, and how does complexity help me decide' concept. That last one is what is colloquially known as 'big O analysis', whereas technically that term is reserved for something else indeed. I'll readily admit that when I first made my GP comment, I didn't really clearly make that distinction in my mind either, which is probably what is the real underlying issue I was trying to point out.

[umanwizard]

This is wrong. Big-O can be used to talk about any function you like, whether best case of an algorithm, worst case, average case for uniform inputs, average case over some different distribution of inputs, how many branch mispredicts a Skylake core hits while running the code on backwards sorted input, the median price of a Big Mac as a function of a country's GDP per capita, or anything else.

[UncleMeat]

Big O is not "worst case scenario". It describes an upper bound on functions. You can absolutely compute the Big O of the average case runtime of an algorithm.