While considering O(log(N)) for time complexity, what is the base of log?
+12
A:
All logarithms are related by some constant. (Hence the change-of-base formula). Because we generally disregard constants in complexity analysis, the base doesn't matter.
Usually, the base is considered to be 2, when deriving the algorithm. Consider a sort like merge sort. You can construct a tree out of it, and the tree has a height of log₂ n, because each node has two branches.
GMan
2009-11-11 04:52:07
+7
A:
It doesn't matter, the relative complexity is the same regardless of the base used.
Rob Walker
2009-11-11 04:52:29
Hmmm. If you logically extend this statement, you would be saying that O(n^2) is the same relative complexity as O(n^3).
Andrew Shepherd
2009-11-11 04:55:20
Not at all. Big diff between 1 million squared or cubed. But log2, log10, log100? Not much difference at all.
cletus
2009-11-11 04:56:37
@Andrew Shepherd - That is not correct. log_a(2n) / log_a(n) = log_b(2n) / log_b(n) for any a and b
mobrule
2009-11-11 04:59:37
@Andres Shepherd: To expand on the other responses to your comment, log_a(n)/log_b(n) is a constant which is the same for all values of n. The ratio of (n^2)/(n^3), on the other hand, grows as n grows. Algorithmic complexity analysis is concerned with how resource requirements increase as n increases, so constants don't matter. Values that vary with n do.
Dave Sherohman
2009-11-16 13:26:55