PDA

View Full Version : Question 39: Quicksort vs Linear Search



Kleid-0
04-17-2005, 07:38 AM
Would you rather wait for the results of a quicksort, a linear search, or a bubble sort on a 200000 element array?

Quicksort
Linear Search
Bubble Sort The answer is linear search but I believe this question is hard to answer because I don't know if the results are coming from a sorting algorithm or a search. If we're talking about a sort the answer would be quicksort, and if we're searching it would obviously be linear search, am I right?

Perspective
04-17-2005, 10:47 AM
A linear search is O(n). Quick sort is O(n log(n)) [in its best case]. Bubble sort is O(n^2).

Which is the shortest of those three? O(n)

Whether your searching or sorting is irrelevant. The point of the question is to see which algorithm runs in the fastest time.

adrianxw
04-17-2005, 11:03 AM
<pedant>Without a statement that says the dataset is not in order, the question is meaningless.</pedant>