Is Binary Search O(log n) or O(n log n)?

Question

I have encountered times when it was O(log n), and times when it was O(n log n). This is also a very popular interview question. So when the interviewer blindly asks you what is the run time of a binary search (with no context)? What should you say?

Answer 1

Sounds like a trick question, since there is no context. Looks like interviewer wants to cover cases when binary search is good, and when its not.

So, binary search is great when you have sorted list of elements and you search for single element, and in such case it costs O(logn).

Now, if we don't have sorted array, cost of sorting it is O(n logn), and then you can apply first case. In such case, its better to place values in set or map and then search (execution time will be O(n) for inserting, O(1) for search).

Both of this cases rests on single search. Binary search is not for searching n elements in single execution (or any number of elements depending on n, like n/2 elements, n/4, or even logn elements - for fixed number its ok). For such cases, there are better ways (sets and maps).

Answer 2

O(log n), for average and worst case. Never heard someone claim it is O(n log n).