You are comparing the time that is needed to perform an initial sort (cost: n*log(n)
) and subsequent binary search (cost: log(n)
). So, if you want to search s
times, you will pay an initial n*log(n)
to sort the list and log(n)
for each (binary) search. That is to say:
c1 = (n*log(n)) + (s*log(n)) = (n+s)*log(n)
Instead, if you perform linear search, there is no "initial cost", but each search will cost you n
, so for s
searches:
c2 = s*n
Obviously, for s
and n
small enough, c2
is smaller because there is no such initial cost, but it grows faster than c1
. At a certain point c1
and c2
will cross. That is to say, c1 = c2
.
n * log(n)
s * n = (n + s) * log(n) --> s * (n - log(n)) = n * log(n) --> s = ------------
n - log(n)
Well, you now have to discuss the equation above. This plot should tell you everything: