Re: A question: Is 200,000 element array worth sorting and search?

mike-yue said:

> The topic comes from a question:
> 
> Would you rather wait for the results of a quicksort, a linear search,
> or a bubble sort on a 200000 element array?
> 1> Quicksort
> 2> Linear Search
> 3> Bubble Sort
> 
> The answer is 2> Linear Search
> 
> Could someone explain why Linear Search, not the other two options?
> Or I misunderstood the original question?

The question is testing your knowledge of algorithmic complexity.

As the number of data items rises (especially past the limit where you can

reasonably think of all numbers as being basically the same size), you can

begin to ignore minor factors like the cost of overheads (e.g. opening a 
file) and even, to some extent, the machine speed! All that matters, for 
large N, is how this N affects the algorithm.

Quicksort is O(N * log N). Linear search is O(N). Bubble sort is O(N * N).

To understand, plot the graphs.

-- 
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www.
+rjh@[EMAIL PROTECTED]
 users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999