Why dynamic memory is needed in C++ - Performance Analysis

Time Complexity: Why dynamic memory is needed

O(n)

Understanding Time Complexity

We want to understand why programs sometimes need dynamic memory instead of fixed memory.

How does using dynamic memory affect how long a program takes to run?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <iostream>

int main() {
    int n;
    std::cin >> n;
    int* arr = new int[n];  // allocate dynamic array
    for (int i = 0; i < n; i++) {
        arr[i] = i * 2;
    }
    delete[] arr;
    return 0;
}
    

This code reads a number n, creates an array of size n in dynamic memory, fills it, then frees it.

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 times the loop runs grows the same way.

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

Pattern observation: The work grows directly with the input size.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Dynamic memory allocation itself takes constant time regardless of size."

[OK] Correct: Allocating large dynamic memory can take longer because the system must find enough space and set it up, so time can grow with size.

Interview Connect

Understanding how dynamic memory affects program speed helps you write programs that handle changing data sizes well.

Self-Check

"What if we replaced the for-loop with a recursive function to fill the array? How would the time complexity change?"