Take the 2-minute tour ×

While answering to this question a debate began in comments about complexity of QuickSort. What I remember from my university time is that QuickSort is O(n^2) in worst case, O(n log(n)) in average case and O(n log(n)) (but with tighter bound) in best case.

What I need is a correct mathematical explanation of the meaning of average complexity to explain clearly what it is about to someone who believe the big-O notation can only be used for worst-case.

What I remember if that to define average complexity you should consider complexity of algorithm for all possible inputs, count how many degenerating and normal cases. If the number of degenerating cases divided by n tend towards 0 when n get big, then you can speak of average complexity of the overall function for normal cases.

Is this definition right or is definition of average complexity different ? And if it's correct can someone state it more rigorously than I ?

share|improve this question
In regards to the argument, I think that if you give big-O notation for running time and don't qualify it, then you should be talking about worst case, simply because you are saying that time is bounded by a function with the specified big-O. If time is bounded, that means worst-case time is bounded, by definition of "bound". If you say, "this is O(n log n) average case", though, then that's well-defined and means what you say in this question. –  Steve Jessop Oct 11 '10 at 10:37
Might be worth trying cstheory.stackexchange.com for the question –  Chris S Oct 11 '10 at 11:01
@Chris: although the FAQ for that site says that "typical homework problems in textbooks" are too basic, and I think this is about as basic as that. –  Steve Jessop Oct 11 '10 at 11:29
You'll get a page of mathematical notation on there, not beginner friendly –  Chris S Oct 11 '10 at 13:11
@Chris S: I work as a programmer but did some math in my old time, so it's not really a problem for me. But for others it could indeed be nice to have something more accessible. –  kriss Oct 11 '10 at 13:48
add comment

4 Answers

up vote 4 down vote accepted

If you're looking for a formal definition, then:

Average complexity is the expected running time for a random input.

share|improve this answer
quote please. Wiki article does not really directly relate. –  Unreason Oct 11 '10 at 11:36
actually found it en.wikipedia.org/wiki/Average-case_complexity, +1 for your answer, it seems (if we believe wikipedia), that formal definition is really on random input. –  Unreason Oct 11 '10 at 11:53
also regarding the concept of case vs complexity check en.wikipedia.org/wiki/Best,_worst_and_average_case; and also it seems you use term 'running time' for bounding function. –  Unreason Oct 11 '10 at 11:55
Thanks, it's exactly what I was looking for. –  kriss Oct 11 '10 at 12:22
@Unreason: I linked for people who don't know what expected value means in mathematics. You're right that this article is not related directly to the question. –  ybungalobill Oct 11 '10 at 14:19
add comment

You're right.

Big O (big Theta etc.) is used to measure functions. When you write f=O(g) it doesn't matter what f and g mean. They could be average time complexity, worst time complexity, space complexities, denote distribution of primes etc.

Worst-case complexity is a function that takes size n, and tells you what is maximum number of steps of an algorithm given input of size n.

Average-case complexity is a function that takes size n, and tells you what is expected number of steps of an algorithm given input of size n.

As you see worst-case and average-case complexity are functions, so you can use big O to express their growth.

share|improve this answer
It's not quite right to write f=O(g) if we're being pedantic. Big O is a set, so we should write f \in O(g) –  jhclark Sep 24 '12 at 19:15
@jhclark: It's a very strong custom to write = when using big O, see en.wikipedia.org/wiki/Asymptotic_notation#Equals_sign or Concrete Mathematics on asymptotic notation. In fact I have never seen any textbook that uses \in except to point out this pecularity. –  sdcvvc Sep 24 '12 at 21:55
Agreed that it's customary -- I'm being pedantic. However, as wikipedia says, many consider "f = O(g) to be an abuse of notation since pure mathematics typically defines = to indicate a bidirectional equality. I'm definitely in the camp that considers this use of = to be rather odious. –  jhclark Sep 26 '12 at 1:18
add comment

I think your definition is correct, but your conclusions are wrong.

It's not necessarily true that if the proportion of "bad" cases tends to 0, then the average complexity is equal to the complexity of the "normal" cases.

For example, suppose that 1/(n^2) cases are "bad" and the rest "normal", and that "bad" cases take exactly (n^4) operations, whereas "normal" cases take exactly n operations.

Then the average number of operations required is equal to:

(n^4/n^2) + n(n^2-1)/(n^2)

This function is O(n^2), but not O(n).

In practice, though, you might find that time is polynomial in all cases, and the proportion of "bad" cases shrinks exponentially. That's when you'd ignore the bad cases in calculating an average.

share|improve this answer
OK, I agree with you. I'm really doing exactly what you suggest to compute the complexity of the average. That's even the calculus I had put in comments of the linked question. I was too fast saying we keep the normal case, that's obviously not always true and depends on the complexity of the degenerating cases. Stated the way I did, the bad case could even continue forever and program never stop and that's definitely not good for average. –  kriss Oct 11 '10 at 10:57
@kriss: yes, the non-halting case is a simpler example than mine, although then it's not technically an "algorithm" you're analysing. –  Steve Jessop Oct 11 '10 at 11:08
add comment

Average case analysis does the following:

Take all inputs of a fixed length (say n), sum up all the running times of all instances of this length, and build the average.

The problem is you will probably have to enumerate all inputs of length n in order to come up with an average complexity.

share|improve this answer
add comment

Your Answer


