Bird
Raised Fist0
Computer Networksknowledge~5 mins

CIDR notation in Computer Networks - Time & Space Complexity

Choose your learning style10 modes available
LearnWhyDeepVisualPracticeChallengeProjectRecallTime
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)
88
1616
2424

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

Practice

(1/5)
1. What does the number after the slash in a CIDR notation represent? For example, in 192.168.1.0/24.
easy
A. The total number of IP addresses in the network
B. The size of the network or how many bits are used for the network part
C. The number of hosts allowed in the network
D. The version of the IP address

Solution

  1. Step 1: Understand CIDR notation structure

    CIDR notation shows an IP address followed by a slash and a number. This number tells how many bits are used for the network part of the address.

  2. Step 2: Interpret the number after the slash

    The number after the slash (like 24 in 192.168.1.0/24) means the first 24 bits are the network portion, defining the network size.

  3. Final Answer:

    The size of the network or how many bits are used for the network part -> Option B

  4. Quick Check:

    Number after slash = network bits [OK]
Hint: Slash number shows network bits, not hosts or total IPs [OK]
Common Mistakes:
  • Confusing slash number with total hosts
  • Thinking slash number is IP version
  • Assuming slash number shows number of hosts
2. Which of the following is the correct CIDR notation for a network with IP address 10.0.0.0 and a subnet mask of 255.255.255.0?
easy
A. 10.0.0.0/16
B. 10.0.0.0/8
C. 10.0.0.0/24
D. 10.0.0.0/32

Solution

  1. Step 1: Convert subnet mask to CIDR prefix length

    Subnet mask 255.255.255.0 means the first 24 bits are ones (11111111.11111111.11111111.00000000), so the CIDR prefix is /24.

  2. Step 2: Match IP with correct CIDR notation

    Given IP 10.0.0.0 with subnet mask 255.255.255.0 corresponds to 10.0.0.0/24.

  3. Final Answer:

    10.0.0.0/24 -> Option C

  4. Quick Check:

    255.255.255.0 = /24 [OK]
Hint: Count 1 bits in subnet mask to find slash number [OK]
Common Mistakes:
  • Confusing /16 with 255.255.0.0 mask
  • Using /32 which means single IP
  • Mixing up subnet mask and CIDR prefix
3. Given the CIDR notation 192.168.10.0/28, how many usable IP addresses are available in this subnet?
medium
A. 14
B. 28
C. 30
D. 16

Solution

  1. Step 1: Calculate total IP addresses from CIDR prefix

    /28 means 28 bits for network, so 32 - 28 = 4 bits for hosts. Total IPs = 2^4 = 16.

  2. Step 2: Calculate usable IP addresses

    Usable IPs exclude network and broadcast addresses, so usable = 16 - 2 = 14.

  3. Final Answer:

    14 -> Option A

  4. Quick Check:

    Usable IPs = 2^(32-28) - 2 = 14 [OK]
Hint: Usable IPs = 2^(32 - slash) minus 2 [OK]
Common Mistakes:
  • Counting total IPs as usable
  • Forgetting to subtract network and broadcast addresses
  • Miscalculating bits for hosts
4. A network administrator wrote the CIDR notation as 172.16.0.0/33. What is wrong with this notation?
medium
A. CIDR prefix must be less than 16
B. IP address is invalid
C. Subnet mask is missing
D. CIDR prefix cannot be greater than 32 for IPv4

Solution

  1. Step 1: Understand CIDR prefix limits for IPv4

    IPv4 addresses are 32 bits long, so CIDR prefix must be between 0 and 32 inclusive.

  2. Step 2: Identify invalid prefix

    A prefix of 33 is invalid because it exceeds the 32-bit length of IPv4 addresses.

  3. Final Answer:

    CIDR prefix cannot be greater than 32 for IPv4 -> Option D

  4. Quick Check:

    IPv4 prefix max = 32 [OK]
Hint: CIDR prefix max 32 for IPv4, 128 for IPv6 [OK]
Common Mistakes:
  • Thinking IP address is invalid instead
  • Confusing CIDR prefix with subnet mask
  • Assuming prefix must be less than 16
5. You need to create a subnet that supports at least 1000 hosts. Which CIDR notation would be the smallest network that fits this requirement?
hard
A. 192.168.0.0/22
B. 192.168.0.0/23
C. 192.168.0.0/21
D. 192.168.0.0/24

Solution

  1. Step 1: Calculate required host bits for 1000 hosts

    Hosts = 2^(host bits) - 2. We want at least 1000 usable hosts. Try host bits: 10 bits gives 2^10 - 2 = 1022 hosts, which is enough.

  2. Step 2: Calculate CIDR prefix from host bits

    IPv4 has 32 bits total. Network bits = 32 - host bits = 32 - 10 = 22. So /22 supports 1022 hosts.

  3. Step 3: Check options for smallest network

    /22 supports 1022 hosts, /23 supports 510 hosts (too small), /21 supports 2046 hosts (larger than needed), /24 supports 254 hosts (too small). Smallest that fits is /22.

  4. Final Answer:

    192.168.0.0/22 -> Option A

  5. Quick Check:

    Hosts ≥ 1000 -> /22 (1022 hosts) [OK]
Hint: Use 2^(32 - prefix) - 2 ≥ hosts needed [OK]
Common Mistakes:
  • Choosing /23 or /24 which are too small
  • Not subtracting 2 for network and broadcast
  • Picking /21 which is larger than needed
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard