Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

For Prim's and Kruskal's Algorithm there are many implementations which will give different running times. However suppose our implementation of Prim's algorithm has runtime $O(|E| + |V|\cdot \log(|V|))$ and Kruskals's algorithm has runtime $O(|E|\cdot \log(|V|))$.

What is the base of the $\log$?

share|improve this question
8  
It doesn't matter. When they are inside O-notation like this, all logarithms with constant base are equivalent. –  David Eppstein Oct 27 '12 at 21:14
    
That said, if you want to know which base the logarithm is before O-ing it away, you'd have to look/give us the specific implementation. –  Raphael Nov 1 '12 at 22:49
    
See also the question Are log10(x) and log2(x) in the same big-O class of functions? –  Juho Nov 1 '12 at 23:38
add comment

migrated from cstheory.stackexchange.com Nov 1 '12 at 20:47

This question came from our site for theoretical computer scientists and researchers in related fields.

1 Answer

up vote 8 down vote accepted

To expand on what David Eppstein said, you can assume it's in any base.

If the log were initially in base $b$, it is asymptotically the same as if it were in base $k$:

$$O(\log_b n) = O\left(\frac{\log_k n}{\log_k b}\right) = O(\log_k n)$$

because $k$ and $b$ are both constants; $\log_k b = O(1)$.

The logs in any two bases are the same in big-O notation.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.