# How much can you achieve in a century?!

I’ve always wondered how bad could an exponential-time algorithm be? Why are polynomial-time algorithms usually considered tractable compared to exponential- and factorial-time ones? I was recently reviewing Introduction to Algorithms when I came across the only problem in Chapter 1. It asks for the largest size $n$ of a problem that can be solved in unit time by an algorithm that takes $f(n)$ microseconds to run, where a unit of time could be a second, a minute, and so on. Here are the numbers I got:

 1 second 1 minute 1 hour 1 day 1 month $lg~n$ $2^{10^6}$ $2^{6\times10^7}$ $2^{3.6\times10^9}$ $2^{8.64\times10^{10}}$ $2^{2.592\times10^{12}}$ $\sqrt{n}$ $10^{12}$ $3.6\times10^{15}$ $1.296\times10^{19}$ $7.46496\times10^{21}$ $6.718464\times10^{24}$ $n$ $10^6$ $6\times10^7$ $3.6\times10^9$ $8.64\times10^{10}$ $2.592\times10^{12}$ $n~lg~n$ $62746$ $2801417$ $133378058$ $2755147513$ $71870856404$ $n^2$ $1000$ $7745$ $60000$ $293938$ $1609968$ $n^3$ $100$ $391$ $1532$ $4420$ $13736$ $2^n$ $19$ $25$ $31$ $36$ $41$ $n!$ $9$ $11$ $12$ $13$ $15$
 1 year 1 century $lg~n$ $2^{3.1104\times10^{13}}$ $2^{3.1104\times10^{15}}$ $\sqrt{n}$ $9.67458816\times10^{26}$ $9.67458816\times10^{30}$ $n$ $3.1104\times10^{13}$ $3.1104\times10^{15}$ $n~lg~n$ $787089606198$ $67699498463641$ $n^2$ $5577096$ $55770960$ $n^3$ $31448$ $145972$ $2^n$ $44$ $51$ $n!$ $16$ $17$

A picture is worth a thousand words! It’s always useful seeing the numbers than hearing stories about how slow an exponential-time algorithm could be.

This also illustrates how interesting NP-complete problems are. The fact that these seemingly simple problems are exponentially hard and that finding an efficient solution to one of them gives a solution to them all, makes them the most exciting riddles in the history of computer science. What’s more exciting is that while many researchers believe no efficient solution exists for this class of problems, no one has ever been able to prove it! This also reveals why P vs. NP was chosen to be the first of Clay Institue’s seven problems of the millennium.