View Full Version : Question 39: Quicksort vs Linear Search

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?

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?

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.

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