Assume we run Prim’s algorithm when we know all the weights are integers in the range {1, ...W} for W, which is logarithmic in |V|. Can you improve Prim’s running time?

When saying 'Improving', it means to at-least: $$O(|E|)$$

My question is - without using priority queue, is it even possible? Currently, we learned that Prim's runtime is $$O(|E|log|E|)$$

And I proved I can get to O(|E|) when weights are from {1,....,W) when W is constant, but when W is logarithmic in |V|, I can't manage to disprove/prove it.


  • $\begingroup$ Can you credit the source where you encountered this task? How quickly can you sort all of the weights? $\endgroup$
    – D.W.
    Jul 1 '20 at 8:19
  • $\begingroup$ @D.W. A University task. sorting is O(nlogn). How can we prove that something can't run in better time? $\endgroup$
    – Osure
    Jul 1 '20 at 9:16
  • $\begingroup$ Think about all sorting methods you know. Are there any linear-time sorting algorithms that work under any conditions? $\endgroup$
    – D.W.
    Jul 1 '20 at 16:11

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.