A picture of asymptotic growth
Exponential vs. subexponential time
Vertical axis: the growth of the exponent f(n).
Exponential and subexponential growth
A comparison of exponent functions n and square root of n. The chart illustrates that the exponent of a subexponential runtime grows more slowly than a linear exponent.
0
25
50
75
100
0
25
50
75
100
Number of variables, n
Exponent f(n) in 2^f(n)
Exponential: f(n) = n
Subexponential example: f(n) = √n
TEACHING EXAMPLE ONLY · THE CLAIMED SAT BOUND USES A DIFFERENT SUBEXPONENTIAL EXPONENT