MAC addressing in Computer Networks - Time & Space Complexity

Time Complexity: MAC addressing

O(n)

Understanding Time Complexity

When working with MAC addressing, it is important to understand how the process of looking up or managing MAC addresses grows as the network size increases.

We want to know how the time to find or handle a MAC address changes when there are more devices on the network.

Scenario Under Consideration

Analyze the time complexity of the following MAC address lookup process.

function findMacAddress(macTable, targetMac) {
  for (let entry of macTable) {
    if (entry.mac === targetMac) {
      return entry.port;
    }
  }
  return null;
}
    

This code searches through a list of MAC address entries to find the port associated with a target MAC address.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each MAC address entry in the table.
• How many times: Up to once for each entry until the target is found or the list ends.

How Execution Grows With Input

As the number of MAC addresses in the table grows, the time to find one may grow roughly in direct proportion.

Input Size (n)	Approx. Operations
10	Up to 10 checks
100	Up to 100 checks
1000	Up to 1000 checks

Pattern observation: The number of checks grows linearly with the number of MAC addresses.

Final Time Complexity

Time Complexity: O(n)

This means the time to find a MAC address grows directly with the number of addresses stored.

Common Mistake

[X] Wrong: "Finding a MAC address always takes the same time no matter how many devices there are."

[OK] Correct: Because the search checks each entry one by one, more entries mean more time needed.

Interview Connect

Understanding how MAC address lookup time grows helps you explain network device behavior clearly and shows you can think about efficiency in real systems.

Self-Check

"What if the MAC addresses were stored in a hash table instead of a list? How would the time complexity change?"