What Takes 1 Second To Execute in Python

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 sqrt(n) or 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(...):

How big n needs to be for fn to take 1 sec:

?n^nBetween 7 and 8
Factorialn!Between 9 and 10
Log Linearn log n200,000
Logarithmiclog n10 ^ 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.


Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.