- interviewer asks candidate to determine the complexity of some algorithms
- candidate is nervous, has a minor brain-fart and flubs a couple of them
- interviewer evaluates candidate as lacking basic CS knowledge you learn in 1st year of any CS course
Ok in this case we're talking about big-O, but it could really be anything.
I think O notation represents the upper bound, so a complexity of N can also be said as O(N^2) or O(N^3), but that isn't particularly useful.
In other words, if f(x)/g(x) < inf when x->inf, then f(x) = O(g(x)).
Then there's omega-notation (lower bound, f(x)/g(x) > 0) and theta-notation (both lower and upper bound, 0 < f(x)/g(x) < inf).
By my experience, some companies need a competent body in the seat ASAP, and some are looking for world-class engineers.
Think Sears vs Amazon-- which company would know what gold was if they fell into a pile of it?
Also I don't think a company deserves to fail if they've got a bit too much faith in a slightly flawed recruitment process. The entire point of us sharing posts like this on here and discussing them is to learn and even help each other, isn't it?
But if I give a code sample that has three nested for loops over some array and doing string comparisons, the candidate should at least have a vague idea that this might be problematic and could better be solved using sets or maps.