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