2 ms·
Big-O typically refers to worst case when people discuss algorithms, but its definition has nothing to do with runtime, or even algorithms, at all. It was inven
by j2kun 8y ago
Big-O typically refers to worst case when people discuss algorithms, but its definition has nothing to do with runtime, or even algorithms, at all. It was invented by mathematicians decades before computers existed.
It's also more nuanced than the inequality in your correction. It's a statement about limits of functions.
- asrp 8y agoThanks for the clarification. I never really know how much (accuracy) to put in a post. I'm assuming that part of it is what turned some folk away from learning complexity in the first place. (I have intuition but not a firm grasp of what turns people away either.) The implicit default of "worst-case running time" (in the context of algorithm) may actually be the source of errors like the one made in the video. For what its worth, I actually think the lim sup definition is easier because its fewer things to memorize.