Link state routing (OSPF) in Computer Networks - Time & Space Complexity

Time Complexity: Link state routing (OSPF)

O(n^2)

Understanding Time Complexity

When studying link state routing like OSPF, it's important to understand how the time to calculate routes grows as the network gets bigger.

We want to know how the routing algorithm's work increases when more routers and links are added.

Scenario Under Consideration

Analyze the time complexity of the following simplified OSPF routing calculation.

function dijkstra(graph, source) {
  let dist = {};
  let visited = new Set();
  let queue = new PriorityQueue();

  for (let node in graph) {
    dist[node] = Infinity;
  }
  dist[source] = 0;
  queue.enqueue(source, 0);

  while (!queue.isEmpty()) {
    let current = queue.dequeue();
    visited.add(current);

    for (let neighbor in graph[current]) {
      if (!visited.has(neighbor)) {
        let newDist = dist[current] + graph[current][neighbor];
        if (newDist < dist[neighbor]) {
          dist[neighbor] = newDist;
          queue.enqueue(neighbor, newDist);
        }
      }
    }
  }
  return dist;
}
    

This code runs Dijkstra's algorithm to find shortest paths from one router to all others in the network graph.

Identify Repeating Operations

Look at the loops and repeated steps in the code.

• Primary operation: The while loop that picks the next closest router and updates distances.
• How many times: It runs once for each router, and inside it loops over each neighbor connected to that router.

How Execution Grows With Input

As the number of routers (nodes) and connections (edges) grows, the work to find shortest paths increases.

Input Size (n = routers)	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 work grows roughly with the square of the number of routers, meaning doubling routers roughly quadruples the work.

Final Time Complexity

Time Complexity: O(n^2)

This means the time to calculate routes grows roughly with the square of the number of routers in the network.

Common Mistake

[X] Wrong: "The routing calculation time grows linearly as the network grows."

[OK] Correct: Because each router's neighbors must be checked repeatedly, the work grows faster than just adding routers one by one.

Interview Connect

Understanding how routing algorithms scale helps you explain network performance and design choices clearly in real-world situations.

Self-Check

"What if we used a more efficient data structure for the priority queue? How would the time complexity change?"