Time Complexity: Client-server vs peer-to-peer models
O(n) for client-server, O(n^2) for peer-to-peer
0
0
Client-server vs peer-to-peer models in Computer Networks - Performance Comparison
Understanding Time Complexity
When comparing client-server and peer-to-peer models, it's important to understand how the number of operations grows as more devices join the network.
We want to see how the workload changes as the network size increases.
Scenario Under Consideration
Analyze the time complexity of message delivery in these two network models.
// Client-server model
for each client request:
server processes request
server sends response
// Peer-to-peer model
for each peer:
connect to all other peers
exchange data directly
This code shows how requests are handled in client-server and how peers communicate in peer-to-peer networks.
Identify Repeating Operations
Look at what repeats as the network grows.
- Primary operation: In client-server, the server handles each client request one by one.
- How many times: Number of clients (n) times.
- Primary operation: In peer-to-peer, each peer connects to every other peer.
- How many times: Each of the n peers connects to (n-1) others.
How Execution Grows With Input
As the number of devices (n) increases, the work changes differently in each model.
| Input Size (n) | Client-Server Operations | Peer-to-Peer Connections |
|---|---|---|
| 10 | 10 requests handled by server | Each peer connects to 9 others, total ~45 connections |
| 100 | 100 requests handled by server | Each peer connects to 99 others, total ~4,950 connections |
| 1000 | 1000 requests handled by server | Each peer connects to 999 others, total ~499,500 connections |
Pattern observation: Client-server grows linearly with n, peer-to-peer grows much faster, roughly with the square of n.
Final Time Complexity
Time Complexity: O(n) for client-server, O(n2) for peer-to-peer
This means client-server work grows steadily as devices increase, but peer-to-peer work grows much faster because every device talks to every other device.
Common Mistake
[X] Wrong: "Peer-to-peer networks handle more devices just as easily as client-server because all devices share the work."
[OK] Correct: While peers share work, the number of connections grows very fast, making communication more complex and costly as devices increase.
Interview Connect
Understanding how network models scale helps you explain trade-offs clearly and shows you can think about system design beyond just code.
Self-Check
"What if in the peer-to-peer model, each peer only connects to a fixed number of peers instead of all? How would that affect the time complexity?"