Bird
Raised Fist0
AWScloud~5 mins

CIDR blocks and IP addressing in AWS - Time & Space Complexity

Choose your learning style10 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime

Start learning this pattern below

Jump into concepts and practice - no test required

or
Recommended
Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong
Time Complexity: CIDR blocks and IP addressing
O(n)
Understanding Time Complexity

When working with CIDR blocks in AWS, it is important to understand how the number of IP addresses affects operations like subnet creation and IP allocation.

We want to know how the effort or steps grow as the size of the CIDR block changes.

Scenario Under Consideration

Analyze the time complexity of allocating IP addresses within a CIDR block.


// Example: Allocate IP addresses from a CIDR block
const cidrBlock = "10.0.0.0/24";
const totalIPs = 256; // Number of IPs in /24

for (let i = 0; i < totalIPs; i++) {
  allocateIPAddress(cidrBlock, i);
}

This sequence simulates allocating each IP address inside a CIDR block one by one.

Identify Repeating Operations

Identify the API calls, resource provisioning, data transfers that repeat.

  • Primary operation: IP address allocation call inside the CIDR block.
  • How many times: Once for each IP address in the block.
How Execution Grows With Input

As the CIDR block size grows, the number of IP addresses increases exponentially, so the number of allocation operations grows proportionally.

Input Size (CIDR block size)Approx. IPs / Operations
/28 (16 IPs)16
/24 (256 IPs)256
/16 (65,536 IPs)65,536

Pattern observation: The number of operations grows linearly with the number of IP addresses in the CIDR block.

Final Time Complexity

Time Complexity: O(n)

This means the time to allocate IPs grows directly in proportion to the number of IP addresses in the CIDR block.

Common Mistake

[X] Wrong: "Allocating IPs from a CIDR block takes the same time no matter how big the block is."

[OK] Correct: Larger CIDR blocks have more IP addresses, so allocating each one takes more steps, increasing total time.

Interview Connect

Understanding how IP allocation scales with CIDR block size shows you can reason about resource limits and efficiency in cloud networking.

Self-Check

What if we changed from allocating IPs one by one to allocating them in batches? How would the time complexity change?

Practice

(1/5)
1. What does a CIDR block like 192.168.1.0/24 represent in AWS networking?
easy
A. A single IP address 192.168.1.24
B. An invalid IP address range
C. A subnet mask of 255.255.0.0
D. A range of IP addresses from 192.168.1.0 to 192.168.1.255

Solution

  1. Step 1: Understand CIDR notation

    The number after the slash (/24) shows how many bits are fixed for the network part. Here, 24 bits fixed means the first 3 parts (192.168.1) are fixed.

  2. Step 2: Calculate the IP range

    With 24 bits fixed, the last 8 bits can vary from 0 to 255, so the range is 192.168.1.0 to 192.168.1.255.

  3. Final Answer:

    A range of IP addresses from 192.168.1.0 to 192.168.1.255 -> Option D

  4. Quick Check:

    CIDR /24 means 256 addresses [OK]
Hint: Count bits after slash to find IP range size [OK]
Common Mistakes:
  • Confusing CIDR with a single IP
  • Misreading the subnet mask bits
  • Assuming /24 means only 24 addresses
2. Which of the following is the correct CIDR notation for a subnet with 512 IP addresses?
easy
A. /23
B. /25
C. /22
D. /24

Solution

  1. Step 1: Calculate bits needed for 512 addresses

    512 addresses require 9 bits (2^9 = 512) for host part.

  2. Step 2: Determine CIDR prefix

    IPv4 has 32 bits total, so prefix = 32 - 9 = 23. So CIDR is /23.

  3. Final Answer:

    /23 -> Option A

  4. Quick Check:

    512 IPs = 2^(32-23) = 512 [OK]
Hint: Use 32 minus log2(IP count) for CIDR [OK]
Common Mistakes:
  • Choosing /24 which gives only 256 addresses
  • Confusing /22 with 1024 addresses
  • Miscounting bits for hosts
3. Given the CIDR block 10.0.0.0/26, how many usable IP addresses are available for hosts?
medium
A. 64
B. 62
C. 32
D. 30

Solution

  1. Step 1: Calculate total IPs in /26 block

    /26 means 32 - 26 = 6 bits for hosts, so total IPs = 2^6 = 64.

  2. Step 2: Subtract network and broadcast addresses

    Two addresses are reserved (network and broadcast), so usable IPs = 64 - 2 = 62.

  3. Final Answer:

    62 -> Option B

  4. Quick Check:

    Usable IPs = total - 2 [OK]
Hint: Usable IPs = 2^(32 - prefix) - 2 [OK]
Common Mistakes:
  • Counting all IPs as usable
  • Forgetting to subtract network and broadcast
  • Mixing up prefix length and host bits
4. You have a VPC with CIDR block 172.16.0.0/16. You want to create two subnets without overlapping IPs. Which pair of CIDR blocks is valid?
medium
A. 172.16.0.0/17 and 172.16.128.0/17
B. 172.16.0.0/18 and 172.16.64.0/17
C. 172.16.0.0/16 and 172.16.0.0/17
D. 172.16.0.0/15 and 172.16.128.0/17

Solution

  1. Step 1: Understand the VPC range

    172.16.0.0/16 covers IPs from 172.16.0.0 to 172.16.255.255.

  2. Step 2: Check subnet ranges for overlap

    /17 splits the /16 into two halves: 172.16.0.0 to 172.16.127.255 and 172.16.128.0 to 172.16.255.255. These do not overlap.

  3. Final Answer:

    172.16.0.0/17 and 172.16.128.0/17 -> Option A

  4. Quick Check:

    Non-overlapping halves split /16 into two /17s [OK]
Hint: Split CIDR by increasing prefix to avoid overlap [OK]
Common Mistakes:
  • Choosing overlapping CIDRs
  • Using larger CIDR than VPC block
  • Ignoring subnet mask sizes
5. You need to design a VPC with exactly 3 subnets: one public with 100 IPs, one private with 50 IPs, and one isolated with 25 IPs. Which CIDR block allocation fits best inside 10.0.0.0/24 without overlap?
hard
A. 10.0.0.0/24, 10.0.1.0/25, 10.0.2.0/26
B. 10.0.0.0/26, 10.0.0.64/26, 10.0.0.128/26
C. 10.0.0.0/25, 10.0.0.128/26, 10.0.0.192/27
D. 10.0.0.0/26, 10.0.0.64/27, 10.0.0.96/28

Solution

  1. Step 1: Calculate needed CIDR for each subnet

    100 IPs need at least /25 (128 IPs), 50 IPs need /26 (64 IPs), 25 IPs need /27 (32 IPs).

  2. Step 2: Assign CIDRs inside 10.0.0.0/24 without overlap

    10.0.0.0/25 covers 0-127, 10.0.0.128/26 covers 128-191, 10.0.0.192/27 covers 192-223. These fit perfectly without overlap.

  3. Final Answer:

    10.0.0.0/25, 10.0.0.128/26, 10.0.0.192/27 -> Option C

  4. Quick Check:

    Subnet sizes fit and sum within /24 [OK]
Hint: Match subnet size to nearest CIDR block, assign sequentially [OK]
Common Mistakes:
  • Using CIDRs too small for IP needs
  • Overlapping subnet ranges
  • Assigning subnets outside VPC CIDR