[benjamincburns]

And if you were insistent on that answer you wouldn't be doing very well. Profiling a complex system to find bottlenecks is quite helpful. Profiling an implementation of an O(n) algorithm isn't going to tell you how to make it O(log(n)).

[ajuc]

But it can tell me if the problem with typical data is with the constant, or with n. It may be that the O(log(n)) algorithm will be slower for typical input.

But yeah, I wouldn't be insistent about that on a job interview.