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 bestcase 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 averagecase execution complexity which depends on first defining the properties of an "average" input. I think what you're trying to define above is averagecase execution complexity  by definition of the Θ() notation your statement above cannot be true.
BTW mergesort is O(n lg n).
 Menahem
