Quote:
Originally Posted by timhndrxn
Please elaborate a little bit more in the text why this is an issue. It is crucial that the bound be polynomial. So why is 2^N bad, but N^9999 good?

Because exponential kills polynomial. I.e., for any real number a, in the limit N > infinity N^a/2^N goes to zero.