Multiple choice

In Prim's algorithm, it will be reduced to _________ if heap is used to keep.

  1. O(|E|log|V|)

  2. O(VlogE)

  3. O(EV)

  4. O(log V)
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

Prim's algorithm using a binary heap performs O(|E|) extract-min and O(|V|) decrease-key operations, each costing O(log|V|). The dominant term is |E|log|V| because the number of edges is typically greater than vertices. Option B incorrectly writes V as base and E as exponent, while C and D are not the correct complexity for heap-based Prim's.

Keep practicing — related questions