Let’s say you’re writing code, and you plan out one function. You try and figure out what are the constraints on the algorithmic efficiency of this function — how good should your algorithm be? This depends, of course on many things. But less than you’d think. First, let’s assume you are ok with around a billion operations (conveniently, modern Gigahertz processors do about a billion low-level operations per second, so it’s a good first assumption.)
If your algorithm is O(n), that means n can’t be much bigger than a billion.
O(n**2) — n should be no more than the root of a billion — around 30,000.
O(n**3) — n should be no more than the third root of a billion — a thousand.
O(fib(n)) — n should be no more than 43
O(2**n) — a billion is right around 2**30, so n should be no more than 30.
O(n!) — n should be no more than 12
OK, now let’s assume you’re the NSA. You can fund a million cores, and your algorithm parallelizes perfectly. How do these numbers change?
O(n) — trillion
O(n**2) — 30 million
O(n**3) — hundred thousand
O(fib(n)) — 71
O(2**n) — 50
O(n!) — 16
You will notice that the difference between someone with a Raspberry PI and a nation-state espionage agency is important for O(n)/O(n**2) algorithms, but quickly becomes meaningless for the higher order ones. You will also notice log(n) was not really factored in — even in a billion, it would mean the difference between handling a billion and handling a hundred million.
This table is useful to memorize for a quick gut check — “is this algorithm feasible”? If the sizes you plan to attack are way smaller, than yes, if way bigger than no, and if “right around” — that’s where you might need to go to a lower-level language or micro-optimize to get it to work. It is useful to know these things before starting to implement: regardless of whether the code is going to run on a smartwatch or on an NSA data center.
Conveniently, these numbers are also useful for memory performance — whether you need to support a one GB device or if you have a terabyte of memory.