I am dealing with the following statement:

the run time for Dijkstra's on a connected undirected graph with positive edge weights using a binary heap is $\Theta$ of the run time for Kruskal's using union-find.

However, this is false and I fail to see why this is so. Dijkstra's algorithm when using binary heap is $O(|E|\log|V|)$. The same is true for Kruskal's algorithm as its complexity is $O(|E|\log|V|)$.

Hence, can someone reconcile this difference? Are there certain edge cases for when this isn't true, hence making this statement false?

  • 2
    $\begingroup$ 1) Why would you compare running-times of algorithms that compute completely different things? 2) Where does this statement come from? 3) You claim it is false, but you seem to show that the algorithms share the same $O$-class. What makes you claim that they don't share the same $\Theta$-class? 4) You may need to read this. $\endgroup$ – Raphael Nov 7 '16 at 10:21
  • $\begingroup$ This was a statement we were to disprove in class. Hence, why 2 different algorithms are being compared. $\endgroup$ – Jonathan Nov 7 '16 at 15:13
  • $\begingroup$ You have to look in two places. 1) Are these $O$-bounds correct? 2) Are both tight? Or do you have better bounds for one but not the other? $\endgroup$ – Raphael Nov 7 '16 at 15:51
  • $\begingroup$ So my current conclusion is that they are not the same because if it is dense, the time complexity for Djikstra's is $O(|V|^2log|V|)$ while Krushal's is just |E|log|V|. Am I correct? $\endgroup$ – Jonathan Nov 7 '16 at 18:34
  • $\begingroup$ No, special input classes are most certainly not the point here. Unless otherwise specified, you are probably to assume worst-case scenarios. $\endgroup$ – Raphael Nov 7 '16 at 19:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.