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