Dijkstra's algorithm in Data Structures Theory - Time & Space Complexity

Time Complexity: Dijkstra's algorithm

O(n^2)

Understanding Time Complexity

Dijkstra's algorithm finds the shortest path from one point to all others in a network.

We want to know how the time it takes grows as the network gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following simplified Dijkstra's algorithm code.

function dijkstra(graph, start):
  dist = map with all nodes set to infinity
  dist[start] = 0
  visited = empty set
  while there are unvisited nodes:
    current = node with smallest dist not visited
    mark current as visited
    for each neighbor of current:
      if dist[current] + edge_weight < dist[neighbor]:
        dist[neighbor] = dist[current] + edge_weight
  return dist
    

This code finds shortest distances from the start node to all others by updating distances step-by-step.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Selecting the unvisited node with the smallest distance and updating neighbors.
• How many times: This happens once for each node, so about n times where n is number of nodes.

How Execution Grows With Input

As the number of nodes and edges grows, the work to find the closest node and update neighbors grows too.

Input Size (n nodes)	Approx. Operations
10	About 100 to 200 operations
100	About 10,000 to 20,000 operations
1000	About 1,000,000 to 2,000,000 operations

Pattern observation: The operations grow roughly with the square of the number of nodes because each node's neighbors are checked multiple times.

Final Time Complexity

Time Complexity: O(n^2)

This means if you double the number of nodes, the time to run the algorithm roughly quadruples.

Common Mistake

[X] Wrong: "Dijkstra's algorithm always runs very fast regardless of graph size because it just picks the shortest path step-by-step."

[OK] Correct: The algorithm must check many nodes and edges, so as the graph grows, the work grows quickly, especially if implemented without efficient data structures.

Interview Connect

Understanding how Dijkstra's algorithm scales helps you explain your choices and shows you grasp how algorithms behave on bigger problems.

Self-Check

"What if we use a priority queue (min-heap) to select the smallest distance node? How would the time complexity change?"