Not in a single interview ever have I been asked about the runtime of an algorithm. On the other hand it is mentioned in almost every article about interviews for programming jobs. How many companies do actually ask such questions? If your future job is mainly building standard business applications, web sites or whatever, no one cares about theoretical runtimes. If your future job is somewhere in research, game, database or operating system development or some other fancy stuff, no one will care to ask for trivial things like asymptotic runtimes. Personally I think most of the time people - interviewers and article-about-interviews writers - just mention Landau notation because they think it makes them look smart without realizing how trivial it actually is.
All those companies should be care about algorithmic runtime, it's part of performance and scalability. If you're not thinking about that then you're not writing production software.
I ask about runtime at every interview (part of "coding, data structures, and algorithms"). It is most definitely not a trivial concept - how do I define the correct solution to a problem when there are multiple approaches?
The requirements for a correct solution (even simple coding problems) include style, correctness, performance, and scalability.
I meant that Landau notation is a trivial concept, not finding a good algorithm to solve a given problem or determining the runtime of a given algorithm.
If your future job is mainly building standard business applications, web sites or whatever you better be caring about theoretical runtimes.
I ask about runtime whenever I interview someone. It is important, if you ever deal with more than a few things at a time. Exponential goes up pretty quickly.
