Meaning of a big O in an exponent
-
06-04-2021 - |
سؤال
What does this expression f(n) = 2O(n) mean, in an exact formal manner?
المحلول
The statement f(n) = 2^O(n)
is equivalent to
log_2(f(n)) = O(n)
(actually, any logarithm will do), so it means that there is some constant C > 0
such that
log_2(f(n)) <= C*n <=> f(n) <= 2^(C*n)
for all large enough n
. Now, ab*c = (ab)c, so another way to put it is to say
f(n) = O(b^n)
for some b > 0
. This b
could be 1.5
, or 4
, or 1000000000000
, so it doesn't tell you too much. All it gives you is that f
is exponential, so it's asymptotically better than O(n!)
, but it doesn't tell you whether it's pretty bad, bad, really bad or truly catastrophically bad.
لا تنتمي إلى StackOverflow