Network topologies (star, bus, ring, mesh) in Computer Networks - Time & Space Complexity

Time Complexity: Network topologies (star, bus, ring, mesh)

O(n) for bus and ring, O(1) for star and mesh

Understanding Time Complexity

When studying network topologies, it's important to understand how the time to send data grows as the network size increases.

We want to know how the structure affects communication speed and delays.

Scenario Under Consideration

Analyze the time complexity of sending a message across different network topologies.

// Example: Sending a message from one node to another
// in different topologies
function sendMessage(topology, nodes, source, target) {
  switch(topology) {
    case 'star':
      // Message goes from source to central hub, then to target
      return 2; // two steps
    case 'bus':
      // Message travels along the bus until it reaches target
      return distanceOnBus(source, target);
    case 'ring':
      // Message travels around the ring until target
      return distanceOnRing(source, target);
    case 'mesh':
      // Direct connection between source and target
      return 1; // one step
    default:
      return -1; // invalid topology
  }
}

This code models how many steps a message takes to reach its destination in each topology.

Identify Repeating Operations

Look at how many nodes the message passes through before reaching the target.

• Primary operation: Passing the message from one node to the next.
• How many times: Depends on the topology and distance between nodes.

How Execution Grows With Input

As the number of nodes (n) grows, the message travel steps change differently for each topology.

Input Size (n)	Star	Bus	Ring	Mesh
10	2 steps	Up to 9 steps	Up to 5 steps	1 step
100	2 steps	Up to 99 steps	Up to 50 steps	1 step
1000	2 steps	Up to 999 steps	Up to 500 steps	1 step

Pattern observation: Star and mesh topologies keep message steps constant or very low, while bus grows linearly and ring grows roughly linearly with half the maximum distance.

Final Time Complexity

Time Complexity: O(n) for bus and ring, O(1) for star and mesh

This means in bus and ring, message travel time grows with the number of nodes, but in star and mesh, it stays about the same no matter how big the network is.

Common Mistake

[X] Wrong: "All network topologies have the same message travel time regardless of size."

[OK] Correct: Some topologies like bus and ring require messages to pass through many nodes, so time grows with network size, unlike star or mesh.

Interview Connect

Understanding how network design affects message travel time helps you explain real-world trade-offs clearly and confidently.

Self-Check

"What if the mesh topology was only partially connected instead of fully connected? How would the time complexity change?"