Data compression techniques in SCADA systems - Time & Space Complexity

Time Complexity: Data compression techniques

O(n)

Understanding Time Complexity

When we compress data in SCADA systems, we want to know how the time to compress grows as the data size grows.

We ask: How much longer does compression take if the data doubles or triples?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function compressData(data) {
  let compressed = []
  for (let i = 0; i < data.length; i++) {
    let count = 1
    while (i + 1 < data.length && data[i] === data[i + 1]) {
      count++
      i++
    }
    compressed.push({value: data[i], count: count})
  }
  return compressed
}

This code compresses data by counting repeated values in a row and storing the value with its count.

Identify Repeating Operations

• Primary operation: The outer for-loop goes through each data item once.
• How many times: The inner while-loop counts repeated items, but together they cover the whole data once.

How Execution Grows With Input

As data size grows, the loops still process each item once, so time grows steadily with data size.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: The time to compress grows roughly in direct proportion to the data size.

Final Time Complexity

Time Complexity: O(n)

This means the time to compress grows linearly as the data size grows.

Common Mistake

[X] Wrong: "The inner while-loop makes this code take much longer than the data size."

[OK] Correct: The inner loop only counts repeated items and together with the outer loop, each item is processed once, so time grows linearly.

Interview Connect

Understanding how loops work together to process data once is a key skill in analyzing performance for real-world systems like SCADA.

Self-Check

"What if the data was sorted before compression? How would that affect the time complexity?"