Time Complexity: sizeof and memory budgeting
O(n)
0
0
sizeof and memory budgeting in Embedded C - Time & Space Complexity
Understanding Time Complexity
When working with memory in embedded C, it is important to understand how the size of data affects program speed.
We want to see how using sizeof impacts the time it takes to allocate or handle memory.
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
int arr[100];
int total_size = sizeof(arr);
for (int i = 0; i < 100; i++) {
arr[i] = i * 2;
}
This code calculates the total memory size of an array and then fills it with values.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: The for-loop that assigns values to each array element.
- How many times: It runs exactly 100 times, once for each element.
How Execution Grows With Input
As the array size grows, the number of assignments grows the same way.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 assignments |
| 100 | 100 assignments |
| 1000 | 1000 assignments |
Pattern observation: The work grows directly with the number of elements.
Final Time Complexity
Time Complexity: O(n)
This means the time to fill the array grows in a straight line as the array gets bigger.
Common Mistake
[X] Wrong: "Using sizeof inside a loop slows down the program a lot."
[OK] Correct: The sizeof operator is calculated at compile time, so it does not add extra time during the loop.
Interview Connect
Understanding how memory size and loops relate helps you write efficient embedded programs that run well on limited devices.
Self-Check
"What if we used a nested loop to fill a 2D array? How would the time complexity change?"