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

Practice

1. What does a MAC address uniquely identify in a computer network?

easy

A. A network protocol type

B. An IP address on the internet

C. A website domain name

D. A device on a local network

Solution

1. Step 1: Understand the role of MAC addresses

   A MAC address is a unique identifier assigned to network interfaces for communications on the physical network segment.

2. Step 2: Identify what MAC addresses represent

   They identify devices on a local network, not IP addresses or domain names.

3. Final Answer:

   A device on a local network -> Option D

4. Quick Check:

   MAC address = device ID on local network [OK]

Hint: MAC addresses identify devices locally, not IPs or domains [OK]

Common Mistakes:

• Confusing MAC address with IP address
• Thinking MAC identifies websites
• Assuming MAC is a protocol

2. Which of the following is the correct format of a MAC address?

easy

A. 00:1A:2B:3C:4D:5E

B. 192.168.1.1

C. 255.255.255.0

D. http://192.168.1.1

Solution

1. Step 1: Recognize MAC address format

   MAC addresses are shown as six pairs of hexadecimal numbers separated by colons or dashes.

2. Step 2: Match the correct format

   00:1A:2B:3C:4D:5E matches this format: six pairs separated by colons with hex digits.

3. Final Answer:

   00:1A:2B:3C:4D:5E -> Option A

4. Quick Check:

   MAC format = hex pairs separated by colons [OK]

Hint: Look for six hex pairs separated by colons or dashes [OK]

Common Mistakes:

• Confusing MAC with IP address format
• Including URL or protocol parts
• Using decimal numbers instead of hex

3. Given the MAC address AC:DE:48:00:11:22, which part typically identifies the manufacturer?

medium

A. 00:11:22

B. 48:00:11

C. AC:DE:48

D. DE:48:00

Solution

1. Step 1: Understand MAC address structure

   The first three pairs (first 24 bits) of a MAC address identify the manufacturer, called the OUI (Organizationally Unique Identifier).

2. Step 2: Identify the first three pairs

   In AC:DE:48:00:11:22, the first three pairs are AC:DE:48, which represent the manufacturer.

3. Final Answer:

   AC:DE:48 -> Option C

4. Quick Check:

   First 3 pairs = manufacturer ID [OK]

Hint: First 3 hex pairs in MAC show manufacturer [OK]

Common Mistakes:

• Choosing last three pairs as manufacturer
• Mixing pairs in the middle
• Not knowing OUI meaning

4. A network admin sees a MAC address written as 00-1G-2B-3C-4D-5E. What is wrong with this MAC address?

medium

A. It is missing pairs

B. It has an invalid character 'G'

C. It uses colons instead of dashes

D. It has too many pairs

Solution

1. Step 1: Check valid characters in MAC address

   MAC addresses use hexadecimal digits: 0-9 and A-F only.

2. Step 2: Identify invalid character

   The character 'G' is not a valid hex digit, so the MAC address is invalid.

3. Final Answer:

   It has an invalid character 'G' -> Option B

4. Quick Check:

   Hex digits only: 0-9, A-F [OK]

Hint: MAC uses hex digits only; watch for invalid letters [OK]

Common Mistakes:

• Ignoring invalid hex characters
• Confusing dashes and colons as errors
• Counting pairs incorrectly

5. You want to filter a list of devices to only those from a specific manufacturer with OUI 00:1A:2B. Which method best uses MAC addresses to do this?

hard

A. Check if the MAC address starts with '00:1A:2B'

B. Check if the MAC address ends with '00:1A:2B'

C. Check if the MAC address contains '2B:00:1A'

D. Check if the MAC address has '00:1A:2B' anywhere in the middle

Solution

1. Step 1: Understand OUI position in MAC address

   The OUI is always the first three pairs of the MAC address, identifying the manufacturer.

2. Step 2: Choose the correct filtering method

   To filter devices by manufacturer, check if the MAC address starts with the OUI '00:1A:2B'.

3. Final Answer:

   Check if the MAC address starts with '00:1A:2B' -> Option A

4. Quick Check:

   OUI = start of MAC address [OK]

Hint: Filter by checking MAC start for OUI [OK]

Common Mistakes:

• Checking MAC end instead of start
• Looking for OUI in the middle
• Assuming OUI can be anywhere