Years ago, in a job interview, I was asked: When is it worth to sort an array? I remember not being able to answer properly, recently I did an algorithm course, and I come to the conclusion that providing a more "academical" response would have probably got me that job... anyway, it is not possible to fix the past, so far I am trying to formally answer it to myself, currently, this is where I am:
Given an array, the time to search will be
- O(n) if not sorted
- O(log(n)) if sorted
Considering that quick sort sorts in O(n*log(n))
When is it worth to sort an array? It would of course depend on the number of times we are going to search the array.
- Cost of searching x times in sorted array = O(n*log(n)) + [O(log(n)) * x]
- Cost of searching x times in unsorted array = O(n) * x
What would be the value of x?