# Improve Prim's algorithm runtime

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.

Thanks

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