Less Wrong is a community blog devoted to refining the art of human rationality. Please visit our About page for more information.

# army1987 comments on GAZP vs. GLUT - Less Wrong

33 07 April 2008 01:51AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Sort By: Old

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 deleted 07 February 2012 03:30:44PM [-]
Comment author: 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.