Talk:Best, worst and average case

From Wikipedia, the free encyclopedia

Worst case... A person won't know that this refers to sorting algorithms... Does this have any sort of potential as an encyclopedia article? Been a long time since I talked the lingo so I don't feel qualified... --Rgamble

---

This looks like some kind of sorting routine, possibly in C#.

A Java programmer would never write such a travesty. He'd simply call the Arrays.sort() method in the Java API.

Actually the sort below is written in C. And it isn't a travesty at all. Suppose you know that all the elements in an array are between a and b, this sort will run in Θ(max(n, b-a)) time (in many cases, this is equivalent to &Theta(n) time: not too shabby :-) --Hari

---

void pigeonhole_sort ( int *low , int *high , int minvalue , int maxvalue )
{
   /* minvalue and maxvalue can also easily be determined within this function */
   int count , size = maxvalue - minvalue + 1 , *current ;
   bool holes[size] ;
   for ( count = 0 ; count < size ; count++ ) /*Initializing*/
      holes[count] = false ;
   for ( current = low ; current <= high ; current++ ) /*Sorting*/
      holes[(*current)-minvalue] = true ;
   for ( current = low , count = 0 ; count < size ; count++ )
      {
      if ( holes[count] )
         {
         *current = count + minvalue ;
         current++ ;
         }
      }
}

---

Are there quicksort implementations which push the worst case performance below O(n²)? AxelBoldt

Well, the STL uses the "introspection sort", which basically uses a median-of-three pivot, and switches to a true O(n log n) sort if the recursion depth is greater than k*log n, for some k, typically 2. One such O(n log n) algorithm would be a quicksort that uses the true median as the pivot in the partition. Since the true median can be found in O(n) time, and partition is O(n) time, this is O(n log n). However, the constant factor in such a sort would be somewhat large, and hence should be used only if the recursion depth gets out of hand (the STL uses heapsort instead). So, you can achieve O(n log n) with the quicksort structure. --Hari

---

Actually, I am thinking maybe we should just merge this to algorithm or have an article like complexity analysis of algorithm or something. -- Taku 08:15, Mar 30, 2004 (UTC)

[edit] Merge with average performance

I merged this with average performance and did some cleanup. I'll leave any extra work (and this article could use it) for others to do. --Phils 16:01, 20 Oct 2004 (UTC)

---

Linear search on an array has a worst-case performance O(n) (see Big O notation), because in the worst case, the algorithm has to check every element. However, the average running time is O(n/2).

This is a poor example, because O(n/2) is really just O(n) as well in Big O notation (the 1/2 is just a scalar multiple).--Malcohol 13:48, 31 January 2006 (UTC)