title: Meaning of average complexity when using Big-O notation
body: <p>While answering to <a href="https://stackoverflow.com/questions/3893937/c-array-sorting-tips/3893967#3893967">this question</a> a debate began in comments about complexity of QuickSort. What I remember from my university time is that QuickSort is <code>O(n^2)</code> in worst case, <code>O(n log(n))</code> in average case and <code>O(n log(n))</code> (but with tighter bound) in best case.</p>
  
  <p>What I need is a correct mathematical explanation of the meaning of <code>average complexity</code> to explain clearly what it is about to someone who believe the big-O notation can only be used for worst-case.</p>
  
  <p>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.</p>
  
  <p>Is this definition right or is definition of average complexity different ? And if it's correct can someone state it more rigorously than I ?</p>