Time complexity when sorting is done before binary search ... see
Suppose there is an array containing unsorted data and I need to select either linear search or binary search to search. Then which option should you choose? The time complexity for linear search is O (n) and for binary search it is O (log n). But the fastest sorting algorithm gives time complexity O (n * log n). Now I don't know how to "add" the complexity of the two algorithms (if that's the correct word) and hence I am asking this question.
So my question is, is sorting and then binary search better than just linear search, or is it the other way around?
Plus, how can I prove that the case can be using big O notation (I mean "add" and "compare" time complexities)?
Thank you so much for reading !!! It means a lot.
source to share
You don't really "add" complexity. Sorting is, as you say, O (n * log n) and searching is O (log n). If you were doing "normal math" on them, then it would be (n + 1) * log n, which is still n * log n.
When you complete multiple steps, you usually complete the hardest task and name it. After all, when n is large enough, n * log n dwarfs log n.
Think of it this way: when n is 1,000,000, n * log n is 20 million. log n is 20. So what's the difference between 20,000,000 and 20,000,020? The term (log n) is irrelevant. So, (n log n) + (log n) for all intents and purposes is (n log n). Even when n is 100, log n is 7. The (log n) term just doesn't make a difference when n is even moderately large.
In your particular case, if you only need to search the list once, then sequential search is the way to go. If you need to search for it multiple times, then you need to weigh the cost of m queries O (m * n) against the cost of sorting and then search. If you are interested in minimum time and know how many times you will search the list, then you will use sequential search if (m * n) is less than (n * log n). Otherwise, use sort and then binary search.
But this is not the only consideration. Binary search on a sorted list gives you very fast response times, whereas linear search can take a very long time for one item. If you can allow the list to be sorted at run time, then this is probably the best way, because the items will be found (or not found) much faster once the program is running. Sorting the list gives the best response time. It's better to pay the price of sorting during startup than to experience very unpredictable response times while running. Or find out that you need to make more inquiries than you thought.,.
source to share
If you need to do one search, do a linear search. This is clearly better than sorting and then binary search.
But , if you have multiple searches, in most cases you should sort the array first and then apply a binary search to each request.
What for? Let's say you are about to perform O (k) searches . If you do a linear search, you get O (n * k) operations . If you sort first, it will take O (nlogn) + O (klogn) = O ((n + k) logn) operations . What's better? When k is very small (less than logn), it is better to perform a linear search. However, in most cases, you'd better sort first.
source to share
So my question is that sorting and then binary search is better than just linear search
Yes you are right.
Binary search should be used when the array is already sorted. Otherwise, you won't be able to use binary search. If you have a large number of queries, it is best to sort the array first and then apply a binary search. However, if you only have a few queries, perhaps a linear search is sufficient.
As with the big O notation, it is always the "big" part; if you are sorting binary search it will be O (n * lgn). If you're just using linear search, it's O (n). but when counting the number of requests (m), the first approach would be O (n * lgn + m * lgn) and the second would be O (m * n). You can see that if m is large (m = n or m -> n) the second approach will be more difficult than binary search.
source to share