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?"

Practice

1. Which network topology connects all devices to a single central device like a switch or hub?

easy

A. Bus topology

B. Star topology

C. Ring topology

D. Mesh topology

Solution

1. Step 1: Understand the central device concept

   Star topology connects all devices to one central device, which manages communication.

2. Step 2: Compare with other topologies

   Bus uses a single cable, ring connects devices in a circle, mesh connects devices directly to many others.

3. Final Answer:

   Star topology -> Option B

4. Quick Check:

   Central device = Star topology [OK]

Hint: Central device means star topology [OK]

Common Mistakes:

• Confusing bus with star because both use cables
• Thinking ring has a central device
• Mixing mesh with star due to multiple connections

2. Which of the following is the correct description of a bus topology?

easy

A. Devices connected in a closed loop

B. Devices connected to a central hub

C. All devices connected to a single cable

D. Each device connected to every other device

Solution

1. Step 1: Recall bus topology structure

   Bus topology connects all devices along a single communication cable.

2. Step 2: Eliminate other options

   Closed loop is ring, every device connected is mesh, central hub is star.

3. Final Answer:

   All devices connected to a single cable -> Option C

4. Quick Check:

   Single cable = Bus topology [OK]

Hint: Bus means one main cable for all devices [OK]

Common Mistakes:

• Confusing ring (closed loop) with bus
• Thinking mesh is a single cable
• Mixing star's central hub with bus

3. In a ring topology with 5 devices, if one device fails, what happens to the network communication?

medium

A. Communication switches to a central hub

B. Only the failed device loses connection

C. Communication continues normally

D. The entire network communication is disrupted

Solution

1. Step 1: Understand ring topology communication

   Devices are connected in a closed loop; data passes through each device.

2. Step 2: Analyze failure impact

   If one device fails, the loop breaks, stopping communication for all devices.

3. Final Answer:

   The entire network communication is disrupted -> Option D

4. Quick Check:

   One failure breaks ring loop = disruption [OK]

Hint: Ring breaks if one device fails [OK]

Common Mistakes:

• Assuming only failed device loses connection
• Thinking ring has a backup path like mesh
• Confusing with star topology behavior

4. A network uses a mesh topology but experiences frequent data collisions. What is the most likely cause?

medium

A. There is no central device to control traffic

B. Devices are connected in a ring causing loops

C. Devices are connected in a single cable

D. Only one device is connected to the network

Solution

1. Step 1: Understand mesh topology traffic

   Mesh connects devices directly; without control, many devices send data simultaneously.

2. Step 2: Identify cause of collisions

   Without a central controller or protocol, data packets collide causing errors.

3. Final Answer:

   There is no central device to control traffic -> Option A

4. Quick Check:

   No traffic control = collisions in mesh [OK]

Hint: No controller causes collisions in mesh [OK]

Common Mistakes:

• Confusing mesh with bus single cable
• Thinking ring causes collisions here
• Assuming one device can't cause collisions

5. A company wants a network where each device connects to every other device directly for maximum reliability. Which topology should they choose and why?

hard

A. Mesh, because every device connects directly to all others

B. Star, because it uses a central hub for easy management

C. Bus, because it uses a single cable to connect all devices

D. Ring, because devices form a closed loop for data flow

Solution

1. Step 1: Identify topology with direct device-to-device connections

   Mesh topology connects every device directly to all others, ensuring reliability.

2. Step 2: Compare other topologies for reliability

   Star depends on central hub, bus uses one cable, ring forms a loop but not all direct connections.

3. Final Answer:

   Mesh, because every device connects directly to all others -> Option A

4. Quick Check:

   Direct connections = Mesh topology [OK]

Hint: Direct all-to-all connections mean mesh [OK]

Common Mistakes:

• Choosing star for reliability ignoring central point failure
• Thinking bus provides direct connections
• Confusing ring loop with full direct connections