Monday, 21 January 2013
The better algorithm for sorting a set of data has O(nlogn) running time, linear search has O(n) running time and binary search has O(logn) running time, where big O is a notation for expressing running time of algorithms you may treat these running times like n, nlogn, logn.
On the basis of this information, consider the scenario that there is a large set of unsorted data, you need to perform “n” searches on this data. For this you have the following two options.
1. Perform “n” linear searches
2. First sort this data in O(nlogn) time and then perform “n” binary searches.
Which option will you choose? Justify your answer mathematically.
