sizeof and memory budgeting in Embedded C - Time & Space Complexity

Time Complexity: sizeof and memory budgeting

O(n)

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

Practice

1. What does the sizeof operator in embedded C tell you?

easy

A. The number of bytes used by a data type or variable

B. The number of bits in a variable

C. The value stored in a variable

D. The memory address of a variable

Solution

1. Step 1: Understand the purpose of sizeof

   The sizeof operator returns the size in bytes of a data type or variable in memory.

2. Step 2: Differentiate from other concepts

   It does not give the value stored, bits count, or address, only the byte size.

3. Final Answer:

   The number of bytes used by a data type or variable -> Option A

4. Quick Check:

   sizeof = bytes used [OK]

Hint: Remember: sizeof = bytes occupied in memory [OK]

Common Mistakes:

• Confusing bytes with bits
• Thinking sizeof returns variable value
• Mixing sizeof with pointer address

2. Which of the following is the correct syntax to get the size of the int data type in embedded C?

easy

A. sizeof(int);

B. sizeof int;

C. size_of(int);

D. sizeof[int];

Solution

1. Step 1: Recall correct sizeof syntax

   The sizeof operator requires parentheses around the variable or type name.

2. Step 2: Check each option

   sizeof(int); uses sizeof(int); which is correct syntax. Options B and D are invalid syntax, and C is not a valid operator.

3. Final Answer:

   sizeof(int); -> Option A

4. Quick Check:

   Use parentheses with sizeof [OK]

Hint: Always use parentheses with sizeof(variable) [OK]

Common Mistakes:

• Omitting parentheses
• Using square brackets instead of parentheses
• Typing size_of instead of sizeof

3. Consider the code snippet:

char arr[10];
int total_size = sizeof(arr);

What is the value of total_size assuming char is 1 byte?

medium

A. 4

B. 40

C. 1

D. 10

Solution

1. Step 1: Calculate size of array

   The array arr has 10 elements of type char, each 1 byte.

2. Step 2: Multiply element size by count

   Total size = 10 elements * 1 byte = 10 bytes.

3. Final Answer:

   10 -> Option D

4. Quick Check:

   Array size = element count x sizeof(element) = 10 [OK]

Hint: Array size = number of elements x sizeof element [OK]

Common Mistakes:

• Confusing element size with total size
• Assuming int size instead of char
• Using sizeof pointer instead of array

4. What is wrong with this code snippet?

int *ptr;
int size = sizeof(ptr) / sizeof(int);
ptr = malloc(size * sizeof(int));

medium

A. malloc is missing a cast to int*

B. sizeof(int) is incorrect, should be sizeof(ptr)

C. sizeof(ptr) returns pointer size, not array size

D. ptr is not initialized before sizeof

Solution

1. Step 1: Understand sizeof on pointer

   sizeof(ptr) returns the size of the pointer itself (usually 4 or 8 bytes), not the size of the array it points to.

2. Step 2: Identify the error in size calculation

   Dividing pointer size by sizeof(int) does not give the number of elements to allocate.

3. Final Answer:

   sizeof(ptr) returns pointer size, not array size -> Option C

4. Quick Check:

   Pointer size ≠ array size [OK]

Hint: sizeof(pointer) gives pointer size, not data size [OK]

Common Mistakes:

• Using sizeof(pointer) to find array length
• Forgetting malloc returns void* needing cast (in C++)
• Assuming pointer is initialized before sizeof

5. You have a memory budget of 73 bytes. You want to store an array of 16-bit integers (short) and a struct:

struct Data {
  char flag;
  int value;
};

If short is 2 bytes, char 1 byte, and int 4 bytes, what is the maximum number of short elements you can store if you also need space for 5 Data structs?

hard

A. 22

B. 24

C. 26

D. 28

Solution

1. Step 1: Calculate size of one Data struct

   Size = size of char + size of int = 1 + 4 = 5 bytes.
   Assuming no padding for simplicity.

2. Step 2: Calculate total size for 5 Data structs

   5 structs x 5 bytes = 25 bytes.

3. Step 3: Calculate remaining memory for shorts

   Total budget 73 bytes - 25 bytes = 48 bytes left.

4. Step 4: Calculate max shorts fitting in remaining memory

   Each short is 2 bytes, so max elements = 48 / 2 = 24 elements.

5. Step 5: Consider struct padding

   Usually, struct Data will be padded to align int at 4 bytes:
   Layout: char flag (1 byte) + 3 bytes padding + int value (4 bytes) = 8 bytes per struct.
   Total for 5 structs = 5 x 8 = 40 bytes.

6. Step 6: Calculate remaining memory with padding

   73 - 40 = 33 bytes left for shorts.

7. Step 7: Calculate max shorts with padding

   33 bytes / 2 bytes per short = 16.5 -> 16 shorts.

8. Step 8: Re-examine options

   Options are larger than 16, so question expects total shorts + structs size ≤ 73.
   Try 24: 24 shorts x 2 bytes = 48 bytes + 5 structs x 8 bytes = 40 bytes -> 88 bytes (too big).

9. Step 9: Reconsider question intent

   Question asks max shorts if 5 structs also stored.
   So total memory = shorts size + structs size ≤ 73 bytes.
   Assuming no padding (5 bytes per struct), total structs = 25 bytes.
   73 - 25 = 48 bytes for shorts -> 48/2 = 24 shorts max.

10. Final Answer:

    24 -> Option B

11. Quick Check:

    Memory budget - structs size = shorts size [OK]

Hint: Subtract struct size from budget, divide remainder by short size [OK]

Common Mistakes:

• Ignoring struct padding/alignment
• Using pointer size instead of actual struct size
• Not subtracting struct memory before shorts calculation