Storage size overview in C - Time & Space Complexity

Time Complexity: Storage size overview

O(n)

Understanding Time Complexity

When we talk about storage size in C, we want to understand how much memory different data types use.

This helps us know how the program's memory needs grow as we use more or bigger data.

Scenario Under Consideration

Analyze the memory size used by different variables in this code snippet.

#include <stdio.h>

int main() {
    int a;
    double b;
    char c;
    int arr[10];
    return 0;
}
    

This code declares variables of different types and an array, each using some memory space.

Identify Repeating Operations

Here, we look at how memory size adds up for each variable and array element.

• Primary operation: Counting memory size of each variable and array elements.
• How many times: Once per variable, and once per array element (10 times for the array).

How Execution Grows With Input

Memory size grows as we add more elements or bigger types.

Input Size (array length)	Approx. Memory Used
10	Size of 10 ints + other variables
100	Size of 100 ints + other variables
1000	Size of 1000 ints + other variables

Pattern observation: Memory grows linearly with the number of array elements.

Final Time Complexity

Space Complexity: O(n)

This means memory size grows in direct proportion to the number of elements we store.

Common Mistake

[X] Wrong: "All variables use the same amount of memory regardless of type or size."

[OK] Correct: Different types like int, double, and char use different amounts of memory, and arrays multiply that by their length.

Interview Connect

Understanding how memory size grows helps you write programs that use memory wisely and avoid surprises in real projects.

Self-Check

"What if we changed the array to hold doubles instead of ints? How would the memory size change?"

Practice

1. Which of the following data types typically uses the least amount of memory in C?

easy

A. int

B. char

C. float

D. double

Solution

1. Step 1: Recall typical sizes of basic data types

   In C, char usually takes 1 byte, int 4 bytes, float 4 bytes, and double 8 bytes.

2. Step 2: Compare sizes to find the smallest

   Since 1 byte is less than 4 or 8 bytes, char uses the least memory.

3. Final Answer:

   char -> Option B

4. Quick Check:

   char = 1 byte [OK]

Hint: Remember char is 1 byte, smallest basic type in C [OK]

Common Mistakes:

• Confusing char with int size
• Assuming float is smaller than char
• Thinking double is smallest

2. Which of the following is the correct way to declare a variable of type double in C?

easy

A. double num;

B. double: num;

C. num double;

D. double-num;

Solution

1. Step 1: Recall C variable declaration syntax

   In C, the type comes first, then the variable name, ending with a semicolon.

2. Step 2: Check each option for correct syntax

   double num; follows this rule: double num;. Others have invalid syntax like colon, reversed order, or invalid characters.

3. Final Answer:

   double num; -> Option A

4. Quick Check:

   Type before name, semicolon ends declaration [OK]

Hint: Type first, then variable name, end with semicolon [OK]

Common Mistakes:

• Using colon instead of semicolon
• Reversing type and variable name
• Using invalid characters like dash

3. Consider the following C code snippet:

printf("%zu", sizeof(long));

What is the expected output on a typical 64-bit system?

medium

A. 8

B. 4

C. 2

D. 16

Solution

1. Step 1: Understand sizeof operator on 64-bit systems

   On most 64-bit systems, long is 8 bytes (64 bits).

2. Step 2: Match the output of sizeof(long)

   The sizeof operator returns the size in bytes, so it returns 8.

3. Final Answer:

   8 -> Option A

4. Quick Check:

   long = 8 bytes on 64-bit [OK]

Hint: On 64-bit, long is usually 8 bytes [OK]

Common Mistakes:

• Assuming long is 4 bytes on 64-bit
• Confusing bits with bytes
• Using wrong format specifier in printf

4. The following code tries to print the size of a short variable but causes a compilation error:

short s;
printf("%d", sizeof(s));

What is the main reason for the error?

medium

A. Variable s is not initialized

B. Missing semicolon after short s

C. Cannot use sizeof on variables

D. Using wrong format specifier for sizeof result

Solution

1. Step 1: Identify the type returned by sizeof

   The sizeof operator returns a value of type size_t, which is an unsigned integer type.

2. Step 2: Check printf format specifier compatibility

   The format specifier %d expects an int, but sizeof returns size_t. The correct specifier is %zu.

3. Final Answer:

   Using wrong format specifier for sizeof result -> Option D

4. Quick Check:

   Use %zu for sizeof output [OK]

Hint: Use %zu to print sizeof results safely [OK]

Common Mistakes:

• Using %d instead of %zu for sizeof
• Thinking sizeof needs variable initialization
• Missing semicolon (actually present)

5. You want to store 1000 integers in an array on a 32-bit system. If int is 4 bytes, how much memory in bytes will the array consume?

hard

A. 2000 bytes

B. 1000 bytes

C. 4000 bytes

D. 8000 bytes

Solution

1. Step 1: Identify size of one integer

   On a 32-bit system, int typically uses 4 bytes.

2. Step 2: Calculate total memory for 1000 integers

   Total memory = number of elements x size of each element = 1000 x 4 = 4000 bytes.

3. Final Answer:

   4000 bytes -> Option C

4. Quick Check:

   1000 x 4 = 4000 bytes [OK]

Hint: Multiply count by size of int (4 bytes) [OK]

Common Mistakes:

• Using size 2 bytes for int
• Multiplying by 8 bytes (double size)
• Confusing bits with bytes