Talk:Best, worst and average case

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science (Rated Start-class, High-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 High  This article has been rated as High-importance on the project's importance scale.
 
WikiProject Mathematics (Rated Start-class, Mid-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Start Class
Mid Priority
 Field: Discrete mathematics

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(n2)? 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)

Merge with average performance[edit]

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)

Removed content from best case[edit]

This kind of analysis differs from the other two in that we consider not the algorithm but the problem itself. It should really be referred to as 'best worse case' analysis, because we aim to arrive at bounds on the performance of all possible algorithmic solutions, assuming their worst case.

Best case analysis is based on a consideration of the logical demands of the problem at hand - what is the very minimum that any algorithm to solve this problem would need to do, in the worst case, for an input of size n?

I don't think you ever do best case analysis on the problem. There will almost always be an algorithm that have a constant best case performance. Taemyr (talk) 18:52, 1 May 2008 (UTC)
This content is confusing "best case" with "lower bounds"; you can very well analyze the best case performance of a specific algorithm over all inputs (see the table in sorting algorithm for example). On the other hand, a lower bound can specify the minimum resources required in the worst case, with the minimum taken over all possible algorithms, a good example being the Ω(n log n) lower bound on comparison sorts. Dcoetzee 21:23, 1 May 2008 (UTC)

Merger proposal[edit]

I propose the three articles Best, worst and average case, Worst-case complexity and Average-case complexity be merged to make one informative and complete article. --Robin (talk) 16:13, 11 August 2009 (UTC)

I'm removing the merge tag. After over three years, there is no discussion on this topic. If you still want to merge, I suggest that you be WP:BOLD and WP:JUSTDOIT. WTF? (talk) 14:02, 24 January 2013 (UTC)

Confusion[edit]

What is worst case space complexity?

Worst case space complexity and worst case performance both link here. It is explained what is worst case perfomance, but what is worst case space complexity? They are different things, because article [|quicksort ] has both of them. —Preceding unsigned comment added by Rmasta (talkcontribs) 22:28, 3 January 2010 (UTC)