2 ms·
They are not different functions. They are the same function. The average case is a special case of the general function in which some of the terms collapse.
by darawk 7y ago
They are not different functions. They are the same function. The average case is a special case of the general function in which some of the terms collapse.
- umanwizard 7y agoI don't know what to say at this point. Any reputable reference will disagree with you, including the two Stack Overflow links I posted, or even the Wikipedia article on big-O notation, which doesn't say anywhere that it has to do with the worst case of algorithms. > They are not different functions. They are the same function. Sure, if you expand the term "function" to include "random variable", which is legitimate to do in some fields of math... but we're talking about deterministic functions from the natural numbers (or real numbers) to the real numbers here. Which is what big-O notation is defined for. Can you write down the deterministic function from N->R giving the "runtime" of some algorithm? (I mean the actual function, not big-O).