CBOR for constrained devices in IOT Protocols - Time & Space Complexity

Time Complexity: CBOR for constrained devices

O(n)

Understanding Time Complexity

When devices with limited power and memory use CBOR to send data, it's important to know how the work grows as data size grows.

We want to see how the time to encode or decode data changes when the data gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following CBOR encoding snippet.

function encodeCBOR(data) {
  let buffer = []
  for (let item of data) {
    buffer.push(encodeItem(item))
  }
  return buffer.concat()
}

function encodeItem(item) {
  // simple encoding logic for one item
  return item.toBytes()
}
    

This code encodes each item in a list into CBOR format one by one, then combines them.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop over each data item to encode it.
• How many times: Once for each item in the input list.

How Execution Grows With Input

As the number of items grows, the encoding work grows in a straight line.

Input Size (n)	Approx. Operations
10	10 encoding calls
100	100 encoding calls
1000	1000 encoding calls

Pattern observation: Doubling the input doubles the work needed.

Final Time Complexity

Time Complexity: O(n)

This means the time to encode grows directly with the number of items to encode.

Common Mistake

[X] Wrong: "Encoding one item takes the same time no matter how many items there are."

[OK] Correct: Each item must be processed separately, so more items mean more total time.

Interview Connect

Understanding how encoding time grows helps you design efficient data handling for small devices, a useful skill in many real projects.

Self-Check

"What if the encodeItem function itself used recursion to encode nested data? How would the time complexity change?"

Practice

1. What is the main advantage of using CBOR on constrained devices?

easy

A. It uses a compact binary format to save space and power

B. It requires a lot of memory to encode data

C. It only works with large servers

D. It converts data into plain text for readability

Solution

1. Step 1: Understand CBOR format purpose

   CBOR is designed to be a compact binary format, which means it uses less space than text formats.

2. Step 2: Relate to constrained devices needs

   Small devices have limited memory and power, so saving space and power is crucial.

3. Final Answer:

   It uses a compact binary format to save space and power -> Option A

4. Quick Check:

   Compact binary = saves space and power [OK]

Hint: CBOR is compact binary, perfect for small devices [OK]

Common Mistakes:

• Thinking CBOR uses more memory
• Assuming CBOR is text-based
• Believing CBOR only works on big servers

2. Which of the following is the correct way to represent an integer value 10 in CBOR hex notation?

easy

A. 0x0F

B. 0x1A

C. 0x18 0A

D. 0x0A

Solution

1. Step 1: Recall CBOR integer encoding

   Small integers 0-23 are encoded directly in the initial byte with major type 0.

2. Step 2: Check hex for integer 10

   Integer 10 fits in 0-23 range, so encoded as 0x0A (major type 0 + value 10).

3. Final Answer:

   0x0A -> Option D

4. Quick Check:

   Small int 10 = 0x0A [OK]

Hint: Small ints 0-23 encoded as single byte 0x00 to 0x17 [OK]

Common Mistakes:

• Using 0x1A which is for 32-bit integers
• Adding extra bytes unnecessarily
• Confusing hex values for different types

3. Given the CBOR byte sequence 0x83 0x01 0x02 0x03, what is the decoded data?

medium

A. [1, 2, 3]

B. {\"1\": 2, \"3\": 4}

C. [0x83, 0x01, 0x02, 0x03]

D. Error: invalid CBOR

Solution

1. Step 1: Interpret initial byte 0x83

   0x83 means array of length 3 (major type 4 + 3).

2. Step 2: Decode following bytes

   Next three bytes 0x01, 0x02, 0x03 are integers 1, 2, 3 respectively.

3. Final Answer:

   [1, 2, 3] -> Option A

4. Quick Check:

   0x83 = array(3), then 1,2,3 [OK]

Hint: 0x80+N means array of length N [OK]

Common Mistakes:

• Confusing array with map
• Reading bytes as hex literals
• Assuming syntax error without checking

4. You try to decode the CBOR data 0xA2 0x01 0x02 0x03 but get an error. What is the likely cause?

medium

A. 0x03 is not a valid CBOR byte

B. Integer keys must be strings in CBOR maps

C. Map length byte 0xA2 says 2 pairs but only 1 pair provided

D. CBOR does not support maps

Solution

1. Step 1: Analyze map length byte 0xA2

   0xA2 means a map with 2 key-value pairs expected.

2. Step 2: Count provided pairs

   Only bytes 0x01 and 0x02 provide one pair; 0x03 is extra byte, so incomplete data.

3. Final Answer:

   Map length byte 0xA2 says 2 pairs but only 1 pair provided -> Option C

4. Quick Check:

   Map length mismatch = error [OK]

Hint: Map length byte must match actual pairs [OK]

Common Mistakes:

• Thinking keys must be strings
• Assuming 0x03 is invalid byte
• Believing CBOR lacks map support

5. You want to encode a sensor reading with temperature 22 and humidity 55 as a CBOR map. Which byte sequence correctly encodes this data?

hard

A. 0xA2 0x01 0x16 0x02 0x37

B. 0xA2 0x6B 0x74 0x65 0x6D 0x70 0x65 0x72 0x61 0x74 0x75 0x72 0x65 0x16 0x68 0x68 0x75 0x6D 0x69 0x64 0x69 0x74 0x79 0x37

C. 0xA1 0x01 0x16 0x02 0x37

D. 0x82 0x16 0x37

Solution

1. Step 1: Understand CBOR map encoding

   0xA2 means a map with 2 key-value pairs.

2. Step 2: Check keys and values encoding

   Keys are text strings: "temperature" (length 11 = 0x6B) and "humidity" (length 8 = 0x68). Values 22 (0x16) and 55 (0x37) are small integers.

3. Step 3: Verify full byte sequence

   Sequence matches map with keys and values correctly encoded as text strings and integers.

4. Final Answer:

   0xA2 0x6B 0x74 0x65 0x6D 0x70 0x65 0x72 0x61 0x74 0x75 0x72 0x65 0x16 0x68 0x68 0x75 0x6D 0x69 0x64 0x69 0x74 0x79 0x37 -> Option B

5. Quick Check:

   Map with 2 text keys and int values = 0xA2 0x6B 0x74 0x65 0x6D 0x70 0x65 0x72 0x61 0x74 0x75 0x72 0x65 0x16 0x68 0x68 0x75 0x6D 0x69 0x64 0x69 0x74 0x79 0x37 [OK]

Hint: Map header 0xA2 + text keys + int values [OK]

Common Mistakes:

• Using array instead of map
• Encoding keys as integers
• Incorrect map length byte