Why IP addressing enables unique identification in Computer Networks - Performance Analysis

Time Complexity: Why IP addressing enables unique identification

O(n)

Understanding Time Complexity

We want to understand how the process of assigning IP addresses scales as the number of devices grows.

Specifically, how does the system ensure each device gets a unique address efficiently?

Scenario Under Consideration

Analyze the time complexity of assigning unique IP addresses in a network.

function assignUniqueIP(devices) {
  let assignedIPs = new Set();
  for (let device of devices) {
    let ip = generateIP();
    while (assignedIPs.has(ip)) {
      ip = generateIP();
    }
    assignedIPs.add(ip);
    device.ip = ip;
  }
}

function generateIP() {
  // Returns a random IP address string
  return Math.floor(Math.random() * 256) + "." +
         Math.floor(Math.random() * 256) + "." +
         Math.floor(Math.random() * 256) + "." +
         Math.floor(Math.random() * 256);
}
    

This code assigns a unique IP address to each device by generating random IPs and checking for duplicates.

Identify Repeating Operations

Look at what repeats as the number of devices increases.

• Primary operation: Looping through each device to assign an IP.
• How many times: Once per device, so as many times as devices exist.
• Duplicate check: For each generated IP, checking if it is already assigned may repeat multiple times if collisions happen.

How Execution Grows With Input

As the number of devices grows, the number of IP assignments grows linearly.

Input Size (n)	Approx. Operations
10	About 10 IP assignments and checks
100	About 100 IP assignments and checks
1000	About 1000 IP assignments and checks

Pattern observation: The work grows roughly in direct proportion to the number of devices.

Final Time Complexity

Time Complexity: O(n)

This means the time to assign unique IPs grows directly with the number of devices.

Common Mistake

[X] Wrong: "Assigning IPs is instant and does not depend on how many devices there are."

[OK] Correct: Each device needs a unique IP, so the system must do work for every device, making the time grow with device count.

Interview Connect

Understanding how unique IP assignment scales helps you think about network design and efficiency, a useful skill in many tech roles.

Self-Check

"What if instead of random IP generation, the system assigned IPs sequentially? How would that affect the time complexity?"