I got curious about what actually is a blocker in terms of time complexity, for python. I’ve always known that the smaller the complexity the better, but it’s never quantitative. How bad is
n^2? How bad is
n^n? How much of an improvement is
log(n)? What is outrageous to write and is absolutely no-go?
Here are some quantitative answers, with my old MacbookPro, what takes 1 second to run in python:
Code to Execute
def fn(n): for _ in range(...): pass
n needs to be for
fn to take 1 sec:
|?||Between 7 and 8|
|Factorial||Between 9 and 10|
|Logarithmic||10 ^ 1,000,000|
So yeah, with my poor little laptop, even just having
O(n) is not particularly a walk in the park, not to mention anything above that.
It’s very rare to encounter something that’s actually
n!, but a total 2 millions of executions, which is equivalent of
O(2^n) capping at n=20,
O(n^2) capping at n=1500, is a pretty quantitative way to measure how efficient something is.