You've just slightly improved upon a very broken way of interviewing engineering candidates. I've been paid by clients happy with the results to do everything from cryptography to writing a compiler / interpreter. Very computer sciencey stuff at times. The devs I work with consistently rate me highly and I often get put in mentoring positions. I couldn't tell you what N^2 is. I learned it in uni. In decades of programming it has come up in many interviews and never once on the job. Maybe in your industry it's important. But if not, please consider re-imagining your interview process. Having hired many developers over my career including at one time for my own business I can assure you there are far better ways at getting high quality signal out of candidates than trying to improve upon what you experienced as a candidate.
"N^2 is bad, except when it isn't" is my take on it.
In uni I maybe had one week of doing O-evaluations, it never came up and I never got interested. I've seen 20,000-word debates on Reddit on whether something is n, n2 or logn... and to my knowledge nobody ever learned anything from those.
In the workplace I've several times ran into the problem of "This is taking way too long," developing tools and methods to measure and drill down, then figure out if it can be improved upon or should be left as-is for now.
Honestly discussions and articles like this leave me absolutely terrified of interviews. My first and only technical interview was my future boss leaving me alone for 30 minutes in a room with a laptop "Code something you like yourself."
> In the workplace I've several times ran into the problem of "This is taking way too long," developing tools and methods to measure and drill down, then figure out if it can be improved upon or should be left as-is for now.
To play devil's advocate, someone with the word Senior in their title would probably have command of recognizing Big O issues, and skip the "this is taking too long" step, and code it efficiently the first time. This is industry dependent, as well, obviously. I've been doing low-latency C++ for 15+ years, and it's not really something you can compromise on.
The mistake, I think, is skipping otherwise good candidates because they don't immediately see these issues. We should put more emphasis on identifying these weaknesses and finding the right mentors to teach them up. We should be hiring more junior and mid level engineers, with the assumption that they will learn and be up to speed in a few years. This has been my approach to interviewing, but I'm often vetoed by other team members.
The problem with Big O complexity is that it just isn't the reason most things are slow. Usually, your input is either so large that you physically can't run a polynomial solution, or your input is so small that it doesn't matter. Speed increases usually come from caching, avoiding indirection, removing slow API calls & properly making use of your hardware.
