Dijkstra’s algorithm can be implemented in two different ways, one of which has a complexity of O(n2) and one of which has a complexity of O(n log n). Choose one of the implementations and briefly justify its complexity.
Try an answer before revealing the guidance below.
Key Concepts
- n iterations
- Finding the minimum-cost node
- Linear scan
- Priority queue (heap)
- Complexity
Answer Approach
- Count how many times the main loop runs.
- Identify the costly step in each iteration.
- Compare a linear search with a heap for that step.
Full Answer
Answer status: Draft answer (unofficial). Revision notes, not an official marking scheme.
Simple implementation, O(n²): the algorithm runs n iterations, adding one node to the set N′ each time. In each iteration it scans every node not yet in N′ to find the one with the least cost, which is n, n−1, …, 1 checks — n(n+1)/2 in total, so O(n²). Heap implementation, O(n log n): keeping the tentative distances in a priority queue (heap) lets each iteration extract the minimum in O(log n) instead of O(n), so n extractions cost O(n log n) (updating neighbours also costs O(log n) each, giving O((n + E) log n) in general).
n + (n − 1) + … + 1 = n(n + 1)/2 → O(n²)Shortcuts: K concepts · A approach · F answer · R reviewed · B bookmark · ← / → previous / next