3 ms·
While these are probably the answers that an interviewer wants, I cringe every time I see someone say that Big O tells you "how long an algorithm takes to run".
by nkurz 12y ago
While these are probably the answers that an interviewer wants, I cringe every time I see someone say that Big O tells you "how long an algorithm takes to run". It's clear the author understands the limitations, but I worry that encouraging people to equate algorithmic complexity with run time in the real world does more harm than good. Big O is fine for theoretical analysis, and at one point it was a reasonable approximation for performance, but with current superscalar SIMD processors with several layers of cache, the gap between theory and practice is getting pretty wide.
Big O tells you (to within some smaller order terms) how many more operations an algorithm needs to perform if you double the size of the input from really big to really, really big. This corresponds to increase in run time at small scale only if all else remains equal, which usually it doesn't. And even then, it only tells you the increase for that same algorithm, rather than how to compare the actual run time to other algorithms with different constants.
My hope is that someday Big O will be reserved for theory and programmers will preach something more like the roofline model: http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-134.pdf http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-13...