new operator in C++ - Time & Space Complexity

Time Complexity: new operator

O(n)

Understanding Time Complexity

When we use the new operator in C++, it creates space in memory for data. Understanding how long this takes helps us write faster programs.

We want to know: How does the time to create new memory grow as we ask for more?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int* arr = new int[n];
for (int i = 0; i < n; i++) {
    arr[i] = i * 2;
}

This code creates an array of size n using new and then fills it with values.

Identify Repeating Operations

Look at what repeats in this code.

• Primary operation: The loop that sets each array element.
• How many times: Exactly n times, once for each element.

How Execution Grows With Input

As n grows, the number of steps to fill the array grows the same way.

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

Pattern observation: The work grows directly with the size of the array.

Final Time Complexity

Time Complexity: O(n)

This means the time to fill the array grows in a straight line with the number of elements.

Common Mistake

[X] Wrong: "Using new to create an array is instant and does not depend on size."

[OK] Correct: While new allocates memory quickly, filling or initializing each element takes time proportional to the number of elements.

Interview Connect

Knowing how memory allocation and initialization scale helps you explain program speed clearly and shows you understand how computers handle data.

Self-Check

"What if we replaced the loop with a function that copies values from another array? How would the time complexity change?"

Practice

1. What does the new operator do in C++?

easy

A. Allocates memory dynamically and returns a pointer to it

B. Deletes a variable from memory

C. Declares a normal variable on the stack

D. Copies data from one variable to another

Solution

1. Step 1: Understand the purpose of new

   The new operator is used to allocate memory on the heap during program execution.

2. Step 2: Identify what new returns

   It returns a pointer to the allocated memory so the program can use it.

3. Final Answer:

   Allocates memory dynamically and returns a pointer to it -> Option A

4. Quick Check:

   new = allocate memory [OK]

Hint: Remember: new creates memory and gives a pointer [OK]

Common Mistakes:

• Confusing new with delete
• Thinking new declares stack variables
• Assuming new copies data

2. Which of the following is the correct syntax to allocate an integer using new?

easy

A. int p = new int;

B. int p = new int();

C. int *p = new int[];

D. int *p = new int;

Solution

1. Step 1: Check pointer declaration

   Using new returns a pointer, so the variable must be a pointer type like int *.

2. Step 2: Verify syntax correctness

   int *p = new int; correctly allocates an int and assigns its address to p.

3. Final Answer:

   int *p = new int; -> Option D

4. Quick Check:

   Pointer = new type [OK]

Hint: new returns pointer, so use pointer variable [OK]

Common Mistakes:

• Declaring variable without pointer
• Using parentheses incorrectly
• Assigning new to non-pointer variable

3. What is the output of this code?

int *arr = new int[3]{10, 20, 30};
std::cout << arr[1] << std::endl;
delete[] arr;

medium

A. 20

B. 10

C. 30

D. Runtime error

Solution

1. Step 1: Understand array allocation with new

   The code creates an array of 3 integers with values 10, 20, 30.

2. Step 2: Access the second element

   Array indexing starts at 0, so arr[1] is the second element, which is 20.

3. Final Answer:

   20 -> Option A

4. Quick Check:

   arr[1] = 20 [OK]

Hint: Remember array index starts at 0 [OK]

Common Mistakes:

• Confusing index 1 with index 0
• Forgetting to use delete[] for arrays
• Expecting runtime error without cause

4. Identify the error in this code snippet:

int *p = new int;
*p = 5;
delete p;
delete p;

medium

A. Incorrect use of new operator

B. Missing initialization of pointer

C. Double deletion of the same pointer

D. No error, code is correct

Solution

1. Step 1: Analyze pointer allocation and deletion

   Pointer p is allocated memory and deleted once correctly.

2. Step 2: Check for repeated delete

   Deleting p a second time causes undefined behavior (double deletion error).

3. Final Answer:

   Double deletion of the same pointer -> Option C

4. Quick Check:

   delete twice = error [OK]

Hint: Delete pointer only once to avoid errors [OK]

Common Mistakes:

• Deleting pointer twice
• Not deleting allocated memory
• Confusing delete and delete[]

5. You want to create a dynamic 2D array of integers with 3 rows and 2 columns using new. Which code correctly allocates and deallocates this array?

hard

A. int *arr = new int[3*2];
// use arr
delete arr;

B. int **arr = new int*[3];
for(int i=0; i<3; i++) arr[i] = new int[2];
// use arr
for(int i=0; i<3; i++) delete[] arr[i];
delete[] arr;

C. int **arr = new int[3][2];
// use arr
delete[] arr;

D. int arr[3][2];
// use arr
// no delete needed

Solution

1. Step 1: Allocate 2D array dynamically

   int **arr = new int*[3]; for(int i=0; i<3; i++) arr[i] = new int[2]; // use arr for(int i=0; i<3; i++) delete[] arr[i]; delete[] arr; correctly creates an array of pointers for rows, then allocates each row as an array of ints.

2. Step 2: Properly deallocate memory

   Each row is deleted with delete[], then the array of pointers is deleted with delete[].

3. Final Answer:

   Uses an array of pointers, allocating each row separately -> Option B

4. Quick Check:

   Nested new and delete[] for 2D arrays [OK]

Hint: Use nested new and delete[] for 2D arrays [OK]

Common Mistakes:

• Using delete instead of delete[] for arrays
• Not deleting all allocated rows
• Trying to allocate 2D array with single new incorrectly