Re:A beginner's guide to Big O notation (2009)
by btilly on Thursday May 05, 2016 @01:07PM
(#11637905)
Common mistake. When people say O(2^n) they USUALLY mean something closer to 2^O(n).
The reason is that f(n) = O(g(n)) means that for some constant k and integer N, if N < n then |f(n)| < kg(n). In other words "grows no faster than a constant times". However when you've got exponential growth the slightest of things can cause the exponent to be slightly different, or there to be a small polynomial factor.
That was the case in his example. (The exponent was different.)
The reason is that f(n) = O(g(n)) means that for some constant k and integer N, if N < n then |f(n)| < kg(n). In other words "grows no faster than a constant times". However when you've got exponential growth the slightest of things can cause the exponent to be slightly different, or there to be a small polynomial factor.
That was the case in his example. (The exponent was different.)