Serial protocol design in Raspberry Pi - Time & Space Complexity

Time Complexity: Serial protocol design

O(n)

Understanding Time Complexity

When designing a serial protocol, it's important to understand how the time to send data grows as the amount of data increases.

We want to know how the time needed changes when we send more bytes over the serial connection.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Send data byte-by-byte over serial
void sendData(uint8_t* data, int length) {
  for (int i = 0; i < length; i++) {
    while (!serialReady()) {
      // wait until serial is ready
    }
    serialSendByte(data[i]);
  }
}
    

This code sends each byte of data one at a time, waiting for the serial port to be ready before sending the next byte.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop over each byte in the data array.
• How many times: Exactly once per byte, so 'length' times.

How Execution Grows With Input

As the number of bytes to send increases, the total time grows proportionally.

Input Size (n)	Approx. Operations
10	About 10 waits and sends
100	About 100 waits and sends
1000	About 1000 waits and sends

Pattern observation: Doubling the data doubles the total operations and time.

Final Time Complexity

Time Complexity: O(n)

This means the time to send data grows directly in proportion to the number of bytes you want to send.

Common Mistake

[X] Wrong: "Waiting for the serial port to be ready is a fixed cost and does not affect time growth."

[OK] Correct: The wait happens for every byte sent, so it adds up and grows with the data size, affecting total time.

Interview Connect

Understanding how sending data byte-by-byte affects time helps you design efficient communication protocols and shows you can think about performance in real devices.

Self-Check

"What if we buffered multiple bytes and sent them all at once? How would the time complexity change?"

Practice

1. What is the main purpose of using start and end bytes in a serial protocol?

easy

A. To increase the speed of data transfer

B. To mark the beginning and end of a message

C. To encrypt the message data

D. To compress the message content

Solution

1. Step 1: Understand message framing

   Start and end bytes are special markers that show where a message begins and ends in a data stream.

2. Step 2: Identify their role in communication

   They help the receiver know exactly which bytes belong to one message, avoiding confusion with other data.

3. Final Answer:

   To mark the beginning and end of a message -> Option B

4. Quick Check:

   Start/end bytes = message boundaries [OK]

Hint: Start/end bytes frame messages clearly [OK]

Common Mistakes:

• Thinking start/end bytes encrypt data
• Confusing start/end bytes with speed control
• Assuming they compress data

2. Which of the following is the correct way to represent a start byte in a serial protocol in Python code?

easy

A. start_byte = 02

B. start_byte = '0x02'

C. start_byte = b'\x02'

D. start_byte = "\x02"

Solution

1. Step 1: Understand byte representation in Python

   Bytes are represented with a b prefix and escape sequences like \x02 inside single or double quotes.

2. Step 2: Check each option

   start_byte = b'\x02' uses b'\x02' which is a bytes object with hex value 0x02. start_byte = '0x02' is a string, not bytes. start_byte = 02 is an integer. start_byte = "\x02" is a string, not bytes.

3. Final Answer:

   start_byte = b'\x02' -> Option C

4. Quick Check:

   Bytes need b prefix and hex escape [OK]

Hint: Bytes start with b and use \x for hex [OK]

Common Mistakes:

• Using strings instead of bytes
• Missing the b prefix
• Using decimal numbers instead of bytes

3. Given this Python snippet for a simple serial message:

message = b'\x02HELLO\x03'
start_byte = b'\x02'
end_byte = b'\x03'
if message.startswith(start_byte) and message.endswith(end_byte):
    content = message[1:-1]
else:
    content = b''
print(content)

What will be printed?

medium

A. b'HELLO'

B. b'\x02HELLO\x03'

C. b''

D. HELLO

Solution

1. Step 1: Check message start and end bytes

   The message starts with b'\x02' and ends with b'\x03', so the condition is True.

2. Step 2: Extract content between start and end bytes

   content = message[1:-1] removes the first and last byte, leaving b'HELLO'.

3. Final Answer:

   b'HELLO' -> Option A

4. Quick Check:

   Strip start/end bytes = b'HELLO' [OK]

Hint: Slice message to remove start/end bytes [OK]

Common Mistakes:

• Printing the whole message without slicing
• Forgetting bytes notation in output
• Confusing string and bytes output

4. This code is intended to check if a serial message has a valid checksum byte at the end:

def check_checksum(msg):
    data = msg[:-1]
    checksum = msg[-1]
    calculated = sum(data) & 0xFF
    return checksum == calculated

message = b'\x02ABC\x06'
print(check_checksum(message))

What is the error in this code?

medium

A. It includes the start byte in checksum calculation

B. It does not convert checksum to integer

C. It uses bitwise AND instead of modulo

D. It compares checksum with data instead of sum

Solution

1. Step 1: Analyze checksum calculation

   The code sums all bytes except the last one, but this includes the start byte (b'\x02'), which usually should be excluded.

2. Step 2: Identify correct checksum range

   Typically, checksum is calculated only on the data bytes, excluding start and end bytes. Here, start byte is wrongly included.

3. Final Answer:

   It includes the start byte in checksum calculation -> Option A

4. Quick Check:

   Exclude start byte from checksum [OK]

Hint: Exclude framing bytes from checksum sum [OK]

Common Mistakes:

• Including start/end bytes in checksum
• Confusing bitwise AND with modulo
• Not converting bytes to int before sum

5. You want to design a serial protocol message with this format: start byte (0x7E), payload (ASCII text), checksum (sum of payload bytes mod 256), and end byte (0x7F). Which Python code correctly builds this message for payload = b'HELLO'?

hard

A. payload = b'HELLO'
start = b'\x7E'
end = b'\x7F'
checksum = sum(payload) & 0xFF
message = start + payload + checksum + end

B. payload = b'HELLO'
start = b'\x7E'
end = b'\x7F'
checksum = sum(payload) % 256
message = start + payload + checksum + end

C. payload = b'HELLO'
start = b'\x7E'
end = b'\x7F'
checksum = bytes([sum(payload)])
message = start + payload + checksum + end

D. payload = b'HELLO'
start = b'\x7E'
end = b'\x7F'
checksum = bytes([sum(payload) % 256])
message = start + payload + checksum + end

Solution

1. Step 1: Calculate checksum correctly

   Checksum is sum of payload bytes modulo 256, so sum(payload) % 256 is correct.

2. Step 2: Convert checksum to bytes and build message

   Checksum must be a single byte, so bytes([value]) converts it properly. Then concatenate start, payload, checksum, and end bytes.

3. Final Answer:

   payload = b'HELLO' start = b'\x7E' end = b'\x7F' checksum = bytes([sum(payload) % 256]) message = start + payload + checksum + end -> Option D

4. Quick Check:

   Checksum as bytes and modulo 256 [OK]

Hint: Use bytes([sum(payload) % 256]) for checksum [OK]

Common Mistakes:

• Not converting checksum to bytes
• Using bitwise AND instead of modulo
• Concatenating int with bytes directly