Problem Detail: 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$?
Asked By : CodeKingPlusPlus
Answered By : SamM
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) = Oleft(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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/6435
