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

Practice

1. Why do we need dynamic memory in C++ programs?

easy

A. To write code without any variables

B. To allocate memory during program execution when size is unknown

C. To avoid using any memory at all

D. To make the program run faster by using fixed memory

Solution

1. Step 1: Understand memory allocation timing

   Static memory is fixed before running, but dynamic memory is allocated while the program runs.

2. Step 2: Recognize the need for unknown sizes

   When the amount of data is not known before running, dynamic memory allows flexible allocation.

3. Final Answer:

   To allocate memory during program execution when size is unknown -> Option B

4. Quick Check:

   Dynamic memory = flexible size allocation [OK]

Hint: Dynamic memory = memory decided during program run [OK]

Common Mistakes:

• Thinking dynamic memory is for speed only
• Confusing dynamic with static memory
• Believing dynamic memory avoids variables

2. Which of the following is the correct syntax to allocate an integer dynamically in C++?

easy

A. int *p = new int;

B. int p = new int;

C. int *p = int new;

D. new int = int *p;

Solution

1. Step 1: Recall dynamic allocation syntax

   In C++, dynamic memory for an int is allocated using 'new int' and assigned to an int pointer.

2. Step 2: Check pointer declaration

   The pointer must be declared as 'int *p' to hold the address of the allocated int.

3. Final Answer:

   int *p = new int; -> Option A

4. Quick Check:

   Pointer = new type; correct syntax [OK]

Hint: Use 'int *p = new int;' for dynamic int allocation [OK]

Common Mistakes:

• Missing pointer * in declaration
• Wrong order of new and type
• Assigning new int to non-pointer variable

3. What will be the output of this C++ code snippet?

int *arr = new int[3];
arr[0] = 10;
arr[1] = 20;
arr[2] = 30;
std::cout << arr[1] << std::endl;
delete[] arr;

medium

A. 10

B. 30

C. Compilation error

D. 20

Solution

1. Step 1: Understand array allocation and assignment

   Dynamic array of size 3 is created, and values 10, 20, 30 are assigned to indices 0, 1, 2 respectively.

2. Step 2: Identify output statement

   The code prints arr[1], which holds the value 20.

3. Final Answer:

   20 -> Option D

4. Quick Check:

   arr[1] = 20 printed [OK]

Hint: Index 1 of array holds 20, so output is 20 [OK]

Common Mistakes:

• Confusing index positions
• Forgetting to use delete[] for arrays
• Assuming compilation error due to dynamic array

4. Identify the error in this C++ code snippet:

int *p;
p = new int(5);
std::cout << *p << std::endl;
// missing delete statement

medium

A. Missing delete to free allocated memory

B. Syntax error in new int(5)

C. Pointer p is not declared

D. Cannot print value using *p

Solution

1. Step 1: Check dynamic allocation correctness

   Pointer p is declared and assigned new int(5), which is correct syntax.

2. Step 2: Identify missing memory management

   Allocated memory is not freed with delete, causing a memory leak.

3. Final Answer:

   Missing delete to free allocated memory -> Option A

4. Quick Check:

   Always delete after new to avoid leaks [OK]

Hint: Always pair new with delete to free memory [OK]

Common Mistakes:

• Ignoring memory leaks
• Thinking new int(5) is wrong syntax
• Assuming pointer must be initialized differently

5. You want to store user input numbers but don't know how many will be entered. Which approach using dynamic memory is best?

hard

A. Use only static variables to store numbers

B. Use a fixed-size array of 100 elements

C. Use a dynamically allocated array and resize it as needed

D. Use a pointer without allocating memory

Solution

1. Step 1: Understand the problem of unknown input size

   Since the number of inputs is unknown, fixed-size arrays may waste memory or be too small.

2. Step 2: Choose flexible memory allocation

   Dynamically allocated arrays can be resized (e.g., by allocating new larger arrays and copying data) to fit input size.

3. Final Answer:

   Use a dynamically allocated array and resize it as needed -> Option C

4. Quick Check:

   Dynamic resizing fits unknown input sizes [OK]

Hint: Resize dynamic array to fit unknown input size [OK]

Common Mistakes:

• Using fixed arrays that may overflow
• Not allocating memory before use
• Ignoring memory management when resizing