VPC peering in GCP - Time & Space Complexity

Time Complexity: VPC peering

O(n²)

Understanding Time Complexity

When connecting two private networks in the cloud, it is important to understand how the time to establish and maintain these connections grows as the number of networks increases.

We want to know how the work involved changes when more networks are linked together using VPC peering.

Scenario Under Consideration

Analyze the time complexity of creating VPC peering connections between multiple networks.

// Example: Creating VPC peering connections
for each VPC in list_of_vpcs:
  for each other_vpc in list_of_vpcs:
    if VPC != other_vpc:
      create_peering_connection(VPC, other_vpc)
      accept_peering_connection(other_vpc, VPC)

This sequence creates peering connections between every pair of VPC networks in the list.

Identify Repeating Operations

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

• Primary operation: API calls to create and accept peering connections between pairs of VPCs.
• How many times: For each pair of distinct VPCs, two API calls are made (one to create, one to accept).

How Execution Grows With Input

As the number of VPCs increases, the number of peering connections grows quickly because each VPC connects to every other VPC.

Input Size (n)	Approx. API Calls/Operations
10	180 (each of 10 VPCs peers with 9 others, 2 calls each)
100	19,800
1000	1,998,000

Pattern observation: The number of operations grows roughly with the square of the number of VPCs, because each VPC connects to all others.

Final Time Complexity

Time Complexity: O(n²)

This means that if you double the number of VPCs, the work to create all peering connections roughly quadruples.

Common Mistake

[X] Wrong: "Adding more VPCs only increases peering work a little bit because each VPC only connects once."

[OK] Correct: Each VPC must connect to every other VPC, so the total number of connections grows much faster than the number of VPCs.

Interview Connect

Understanding how connection work grows helps you design cloud networks that scale well and avoid unexpected delays.

Self-Check

"What if we only connect each VPC to a fixed number of other VPCs instead of all? How would the time complexity change?"