Why networks enable communication and resource sharing in Computer Networks - Performance Analysis

Time Complexity: Why networks enable communication and resource sharing

O(n²)

Understanding Time Complexity

We want to understand how the time needed for communication and sharing resources changes as more devices join a network.

How does adding more devices affect the work the network must do?

Scenario Under Consideration

Analyze the time complexity of the following network communication process.

for each device in network:
    for each other device in network:
        send message
        share requested resource

This code shows each device sending messages and sharing resources with all other devices in the network.

Identify Repeating Operations

Look at what repeats in the process.

• Primary operation: Each device sends messages and shares resources with every other device.
• How many times: For each device, it repeats for all other devices, so the number of operations grows with the square of the number of devices.

How Execution Grows With Input

As the number of devices increases, the total communication and sharing steps grow quickly.

Input Size (n)	Approx. Operations
10	About 100 (10 x 10)
100	About 10,000 (100 x 100)
1000	About 1,000,000 (1000 x 1000)

Pattern observation: When the number of devices doubles, the work needed grows about four times, showing a fast increase.

Final Time Complexity

Time Complexity: O(n²)

This means the work to communicate and share resources grows quickly as more devices join, roughly by the square of the number of devices.

Common Mistake

[X] Wrong: "Adding more devices only increases work a little bit, so time grows linearly."

[OK] Correct: Because each device talks to all others, the total work grows much faster than just adding one device at a time.

Interview Connect

Understanding how network communication scales helps you explain real-world challenges in managing many devices efficiently.

Self-Check

"What if devices only communicated with a fixed number of neighbors instead of all devices? How would the time complexity change?"