CIDR notation in Computer Networks - Time & Space Complexity

Time Complexity: CIDR notation

O(n)

Understanding Time Complexity

When working with CIDR notation, it is important to understand how the time to process addresses grows as the network size changes.

We want to know how the number of operations changes when calculating or matching IP addresses using CIDR.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function isInSubnet(ip, cidr) {
  const [subnet, prefixLength] = cidr.split('/');
  const ipBits = ipToBits(ip);
  const subnetBits = ipToBits(subnet);
  for (let i = 0; i < Number(prefixLength); i++) {
    if (ipBits[i] !== subnetBits[i]) {
      return false;
    }
  }
  return true;
}

function ipToBits(ip) {
  return ip.split('.').map(octet => parseInt(octet).toString(2).padStart(8, '0')).join('');
}
    

This code checks if an IP address belongs to a subnet defined by CIDR notation by comparing bits up to the prefix length.

Identify Repeating Operations

• Primary operation: Loop comparing bits of IP and subnet up to prefix length.
• How many times: The loop runs once for each bit in the prefix length (usually between 0 and 32 for IPv4).

How Execution Grows With Input

The number of operations grows directly with the prefix length, which is the number of bits to compare.

Input Size (prefix length)	Approx. Operations (bit comparisons)
8	8
16	16
24	24

Pattern observation: The time grows linearly as the prefix length increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to check if an IP is in a CIDR subnet grows in a straight line with the number of bits compared.

Common Mistake

[X] Wrong: "Checking if an IP is in a CIDR subnet takes the same time regardless of prefix length."

[OK] Correct: The code compares each bit up to the prefix length, so longer prefixes mean more comparisons and more time.

Interview Connect

Understanding how CIDR matching scales helps you explain network filtering and routing decisions clearly and confidently.

Self-Check

"What if we changed the code to compare bytes instead of bits? How would the time complexity change?"