Static memory allocation patterns in Embedded C - Time & Space Complexity

Time Complexity: Static memory allocation patterns

O(n)

Understanding Time Complexity

Let's explore how the time cost behaves when using static memory allocation in embedded C.

We want to know how the program's running time changes as the size of statically allocated data grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#define SIZE 100

int data[SIZE];

void initialize() {
    for (int i = 0; i < SIZE; i++) {
        data[i] = i * 2;
    }
}
    

This code statically allocates an array and fills it with values using a loop.

Identify Repeating Operations

Look for repeated actions in the code.

• Primary operation: The for-loop that assigns values to each array element.
• How many times: Exactly SIZE times, once per element.

How Execution Grows With Input

As the array size grows, the loop runs more times, doing more work.

Input Size (n)	Approx. Operations
10	10 assignments
100	100 assignments
1000	1000 assignments

Pattern observation: The number of operations grows directly with the size of the array.

Final Time Complexity

Time Complexity: O(n)

This means the time to initialize grows in a straight line as the array size increases.

Common Mistake

[X] Wrong: "Static memory allocation means the program runs instantly regardless of size."

[OK] Correct: Even though memory is fixed at compile time, the program still needs to do work for each element during initialization, so time grows with size.

Interview Connect

Understanding how loops over statically allocated arrays affect time helps you explain performance clearly and confidently in real projects.

Self-Check

"What if we replaced the for-loop with a function that initializes only half the array? How would the time complexity change?"