Encapsulation and decapsulation in Computer Networks - Time & Space Complexity

Time Complexity: Encapsulation and decapsulation

O(n)

Understanding Time Complexity

When data moves through a network, it is wrapped and unwrapped in layers. We want to understand how the time to do this wrapping and unwrapping changes as the data or layers increase.

How does the work grow when more layers or bigger data packets are involved?

Scenario Under Consideration

Analyze the time complexity of the following process for encapsulation and decapsulation.

function encapsulate(data, layers) {
  for (let i = 0; i < layers; i++) {
    data = addHeaderAndFooter(data, i);
  }
  return data;
}

function decapsulate(data, layers) {
  for (let i = 0; i < layers; i++) {
    data = removeHeaderAndFooter(data);
  }
  return data;
}
    

This code adds or removes headers and footers layer by layer to data as it moves through the network.

Identify Repeating Operations

Look at what repeats in the code.

• Primary operation: Adding or removing headers and footers for each layer.
• How many times: Once for each layer, repeated in a simple loop.

How Execution Grows With Input

As the number of layers increases, the work to add or remove headers grows in a straight line.

Input Size (layers)	Approx. Operations
10	10 header/footer additions or removals
100	100 header/footer additions or removals
1000	1000 header/footer additions or removals

Pattern observation: The work grows evenly as layers increase, doubling layers doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to encapsulate or decapsulate grows directly with the number of layers.

Common Mistake

[X] Wrong: "Adding more layers does not affect time much because each layer is small."

[OK] Correct: Even small layers add work, and more layers mean more repeated steps, so time grows steadily with layers.

Interview Connect

Understanding how work grows with layers helps you explain network processing clearly and shows you can think about efficiency in real systems.

Self-Check

"What if the data size also grows with each layer? How would the time complexity change?"