VietMX Staff asked 3 years ago
Problem
If you had an unsorted list of one million unique items, and knew that you would only search it once for a value, which of the following algorithms would be the fastest?
- Use linear search on the unsorted list
- Use insertion sort to sort the list and then binary search on the sorted list
Linear search takes just O(n), while sorting a list first takes O(n log n). Since you are going to search the list only once for a value, the fact that subsequent searches in the sorted list with a binary search takes only O(log n) does not help overcome the overhead of the O(n log n) time complexity involved in the sorting, and hence a linear search would be more efficient for the task.
