Comment author:[deleted]
07 February 2012 11:52:36AM
7 points
[-]

Likewise, EXPTIME doesn't mean Large EXPTIME -- an algorithm running in exp(1e-15*N) seconds is asymptotically slower than one running in N^300 seconds, but it is faster for pretty much all practical purposes.

I once read an Usenet post or Web page along the lines of “There are two kinds of numbers: those smaller than Graham's number and those larger than Graham's number. Computational complexity theory traditionally only concerns itself with the latter, but only the former are relevant to real-world problems.”

Comment author:kilobug
07 February 2012 03:39:37PM
*
1 point
[-]

No, slower. N^300 is polynomial, exp(1e-15*N) is exponential.

Maybe it's easier to understand them if you take log ? log(N^300) = log(N) * 300 and log(exp(1e-15 * N)) = 1e-15 * N

Whatever >0 multiplicative constants a and b you put, a * N will at one point become bigger (so, slower) than b * log(N). In this, that'll happen roughly when N will be somewhat above 10^15, around 10^20 according to a simple guess.

## Comments (166)

OldLikewise, EXPTIME doesn't mean Large EXPTIME -- an algorithm running in exp(1e-15*N) seconds is asymptotically slower than one running in N^300 seconds, but it is faster for pretty much all practical purposes.

I once read an Usenet post or Web page along the lines of “There are two kinds of numbers: those smaller than Graham's number and those larger than Graham's number. Computational complexity theory traditionally only concerns itself with the latter, but only the former are relevant to real-world problems.”

Comment deleted07 February 2012 03:30:44PM [-]*1 point [-]No, slower. N^300 is polynomial, exp(1e-15*N) is exponential.

Maybe it's easier to understand them if you take log ? log(N^300) = log(N) * 300 and log(exp(1e-15 * N)) = 1e-15 * N

Whatever >0 multiplicative constants a and b you put, a * N will at one point become bigger (so, slower) than b * log(N). In this, that'll happen roughly when N will be somewhat above 10^15, around 10^20 according to a simple guess.