|
in reply to Re: Re: An informal introduction to O(N) notation
in thread An informal introduction to O(N) notation
While we're nitpicking:
O() defines an upper bound (typically, but not exclusively, on worst case behaviour)
Ω() defines a lower bound (again typically, but not exclusively, on best-case behaviour)
An algorithm is said to run in Θ(f(n)) if it runs in O(f(n)) and in Ω(f(n)), i.e. the upper and lower bounds are no more than a constant multiple of each other. It is a tighter definition than average-case execution complexity which depends on first defining the properties of an "average" input. I think what you're trying to define above is average-case execution complexity - by definition of the Θ() notation your statement above cannot be true.
BTW mergesort is O(n lg n).
- Menahem
|
