3 ms·

Please see https://en.wikipedia.org/wiki/Best,_worst_and_average_case https://en.wikipedia.org/wiki/Best,_worst_and_average_case Big-O is valid notation for _m

by jo909 10y ago

Please see https://en.wikipedia.org/wiki/Best,_worst_and_average_case https://en.wikipedia.org/wiki/Best,_worst_and_average_case Big-O is valid notation for _many aspects_ of an algorithm. The author applied it to a very practical one and explained what exactly he describes very well.

reikonomusha 10y ago
I think it's a massive and needless abuse of standard computer science terminology to re-define it as something completely different.
- MrManatee 10y ago
  I'm not entirely sure what you are referring to. You might be referring to the fact that the author's definition of big-O doesn't say anything about constant factors or asymptotics. This makes the definition incorrect, or at least sloppy. But judging by usage, it seems that he actually knows and is using the standard definition. The error is just in that one sentence, and it doesn't affect the rest of the argument. You might also be objecting to the fact that he makes a distinction between time and instruction count, and is using big-O notation for both. I don't think there's anything nonstandard about making this distinction when it needs to be made. Take, for example, Karmarkar's algorithm: https://en.wikipedia.org/wiki/Karmarkar%27s_algorithm https://en.wikipedia.org/wiki/Karmarkar%27s_algorithm
DanWaterworth 10y ago
Re-read the article, bearing in mind that O(sqrt n) is a set that contains O(1).
- angry_octet 10y ago
  Yes, but it isn't very helpful to think of it that way, we're not competing to find the weakest constraint.
zeroer 10y ago
The best/worst/average issue is orthogonal to the definition of what big-O means. The time it take an algorithm has best/worst/average cases, and each of these is a function and thus is a member of big-O classes. The definition of big-O has a completely standardized and unambiguous definition, and the author of the article somehow has a four-part blog post on big-O without knowing it.

by jo909 10y ago

reikonomusha 10y ago

I think it's a massive and needless abuse of standard computer science terminology to re-define it as something completely different.

MrManatee 10y ago
I'm not entirely sure what you are referring to. You might be referring to the fact that the author's definition of big-O doesn't say anything about constant factors or asymptotics. This makes the definition incorrect, or at least sloppy. But judging by usage, it seems that he actually knows and is using the standard definition. The error is just in that one sentence, and it doesn't affect the rest of the argument. You might also be objecting to the fact that he makes a distinction between time and instruction count, and is using big-O notation for both. I don't think there's anything nonstandard about making this distinction when it needs to be made. Take, for example, Karmarkar's algorithm: https://en.wikipedia.org/wiki/Karmarkar%27s_algorithm https://en.wikipedia.org/wiki/Karmarkar%27s_algorithm

DanWaterworth 10y ago

Re-read the article, bearing in mind that O(sqrt n) is a set that contains O(1).

angry_octet 10y ago
Yes, but it isn't very helpful to think of it that way, we're not competing to find the weakest constraint.

zeroer 10y ago

The best/worst/average issue is orthogonal to the definition of what big-O means. The time it take an algorithm has best/worst/average cases, and each of these is a function and thus is a member of big-O classes. The definition of big-O has a completely standardized and unambiguous definition, and the author of the article somehow has a four-part blog post on big-O without knowing it.