Why dynamic memory is needed - Performance Analysis

Time Complexity: Why dynamic memory is needed

O(n)

Understanding Time Complexity

We want to understand how using dynamic memory affects the time it takes for a program to run.

Specifically, we ask: How does allocating memory while the program runs impact performance?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <stdlib.h>

int* createArray(int n) {
    int* arr = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        arr[i] = i * 2;
    }
    return arr;
}
    

This code allocates memory for an array of size n during runtime and fills it with values.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for loop that fills the array.
• How many times: It runs n times, once for each element.

How Execution Grows With Input

As n grows, the number of steps to fill the array grows directly with n.

Input Size (n)	Approx. Operations
10	About 10 steps to fill the array
100	About 100 steps to fill the array
1000	About 1000 steps to fill the array

Pattern observation: The work grows evenly as the input size grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to fill the array grows in direct proportion to the number of elements.

Common Mistake

[X] Wrong: "Allocating memory dynamically is instant and does not affect performance."

[OK] Correct: Allocating memory takes time, and filling that memory with values also takes time proportional to the size.

Interview Connect

Understanding how dynamic memory allocation affects time helps you write efficient programs and explain your choices clearly.

Self-Check

What if we changed the loop to fill only half the array? How would the time complexity change?