0
$\begingroup$

I don't understand why O notation is the worst case. If this notations describes a function f such that 0 <= f(n) <= cg(n), we can see that in any case f will be smaller that the original function g that describes the running time. In my idea, f(n) describes a better option because the running time is less for any input n. Someone can explain me please why O notation is the worst case?

$\endgroup$
3
$\begingroup$

It doesn't, if $f \in O(g)$, it "just" tells us that $g$ is an asypmtotic upper bound for $f$.

This tool (asymptotic notation) can then be used to express relationships between the growth rates of functions in any context you want. One of these contexts happens to be the worst case running time of algorithms, so it's not the big-oh that makes it worst case, it's what it's being applied to.

You can quite happily use big-oh to upper bound best-case running time, average-case, in amortised analysis, space usage, or in things that have nothing to do with algorithmic complexity.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.