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@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999