patternCritical
Time complexity of an algorithm: Is it important to state the base of the logarithm?
Viewed 0 times
thetimealgorithmstateimportantcomplexitylogarithmbase
Problem
Since there is only a constant between bases of logarithms, isn't it just alright to write $f(n) = \Omega(\log{n})$, as opposed to $\Omega(\log_2{n})$, or whatever the base might be?
Solution
It depends where the logarithm is. If it is just a factor, then it doesn't make a difference, because big-O or $\theta$ allows you to multiply by any constant.
If you take $O(2^{\log n})$ then the base is important. In base 2 you would have just $O(n)$, in base 10 it's about $O(n^{0.3010})$.
If you take $O(2^{\log n})$ then the base is important. In base 2 you would have just $O(n)$, in base 10 it's about $O(n^{0.3010})$.
Context
StackExchange Computer Science Q#109607, answer score: 68
Revisions (0)
No revisions yet.