Array Insertion at End in DSA C++ - Time & Space Complexity

Time Complexity: Array Insertion at End

O(1)

Understanding Time Complexity

We want to understand how long it takes to add a new item at the end of an array.

How does the time needed change as the array grows bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void insertAtEnd(int arr[], int &size, int capacity, int value) {
    if (size < capacity) {
        arr[size] = value;
        size++;
    }
}
    

This code adds a new value at the end of an array if there is space.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: One assignment to place the new value at the end.
• How many times: Exactly once per insertion.

How Execution Grows With Input

Adding one item always takes the same small number of steps, no matter how big the array is.

Input Size (n)	Approx. Operations
10	1 assignment
100	1 assignment
1000	1 assignment

Pattern observation: The time stays the same as the array grows.

Final Time Complexity

Time Complexity: O(1)

This means adding an item at the end takes a constant amount of time regardless of array size.

Common Mistake

[X] Wrong: "Adding at the end takes longer as the array grows because we have to move all elements."

[OK] Correct: We do not move existing elements when adding at the end; we just place the new item in the next free spot.

Interview Connect

Knowing that adding at the end is fast helps you understand when arrays are a good choice and when other structures might be better.

Self-Check

"What if the array is full and we need to resize it before inserting? How would the time complexity change?"

Practice

1. What happens when you insert an element at the end of a fixed-size array in C++ without resizing?

easy

A. The element replaces the last element if the array is full

B. The array automatically resizes to fit the new element

C. The element is added at the next free position if available

D. The program throws a runtime error

Solution

1. Step 1: Understand fixed-size array behavior

   Fixed-size arrays have a set size and cannot grow automatically.

2. Step 2: Inserting at end when full

   If the array is full, you cannot add a new element without overwriting or causing undefined behavior. If there is space available, the element is added at the next free position.

3. Final Answer:

   The element is added at the next free position if available -> Option C

4. Quick Check:

   Fixed-size array adds element only if space available [OK]

Hint: Fixed arrays don't resize; add element only if space available [OK]

Common Mistakes:

• Assuming array resizes automatically
• Thinking insertion always adds new space
• Expecting runtime error on insertion

2. Which of the following is the correct syntax to insert an element `x` at the end of a vector `v` in C++?

easy

A. v.append(x);

B. v.push_back(x);

C. v.add(x);

D. v.insert_end(x);

Solution

1. Step 1: Recall vector insertion method

   The standard method to add an element at the end of a vector is push_back.

2. Step 2: Check syntax correctness

   Only v.push_back(x); is valid C++ syntax for vector insertion at end.

3. Final Answer:

   v.push_back(x); -> Option B

4. Quick Check:

   Use push_back to insert at vector end [OK]

Hint: Use push_back() to add at vector end [OK]

Common Mistakes:

• Using non-existent methods like insert_end or add
• Confusing vector with other container methods
• Using append which is not a C++ vector method

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

int arr[5] = {1, 2, 3, 4, 5};
int n = 5;
int x = 10;
if (n < 5) {
  arr[n] = x;
  n++;
}
for (int i = 0; i < n; i++) {
  std::cout << arr[i] << " ";
}

medium

A. 1 2 3 4 10

B. 1 2 3 4 5 10

C. Compilation error

D. 1 2 3 4 5

Solution

1. Step 1: Check condition for insertion

   The condition if (n < 5) is false because n equals 5, so insertion does not happen.

2. Step 2: Print array elements

   The loop prints all elements from index 0 to 4, which are 1 2 3 4 5.

3. Final Answer:

   1 2 3 4 5 -> Option D

4. Quick Check:

   Insertion skipped, original array printed [OK]

Hint: Check insertion condition before adding element [OK]

Common Mistakes:

• Assuming insertion happens even if condition false
• Printing beyond array size
• Confusing array size with variable n

4. Identify the error in the following code that tries to insert an element at the end of an array:

int arr[3] = {1, 2, 3};
int n = 3;
int x = 4;
arr[n] = x;
n++;
for (int i = 0; i < n; i++) {
  std::cout << arr[i] << " ";
}

medium

A. Array index out of bounds when inserting element

B. Variable n is not incremented correctly

C. Missing semicolon after arr[n] = x

D. Loop condition should be i <= n

Solution

1. Step 1: Check array size and insertion index

   Array size is 3, valid indices are 0,1,2. Inserting at arr[3] is out of bounds.

2. Step 2: Understand consequences of out-of-bounds access

   Accessing arr[3] causes undefined behavior or runtime error.

3. Final Answer:

   Array index out of bounds when inserting element -> Option A

4. Quick Check:

   Insertion index must be within array size [OK]

Hint: Array indices go from 0 to size-1 only [OK]

Common Mistakes:

• Ignoring array bounds when inserting
• Assuming array resizes automatically
• Incorrect loop boundary causing extra prints

5. You have an array `int arr[6] = {1, 2, 3, 4, 5};` and a variable `int n = 5;` representing the current number of elements. Write the correct code snippet to insert `10` at the end safely, considering array size limits.

hard

A. if (n < 6) { arr[n] = 10; n++; }

B. arr[n] = 10; n++;

C. if (n <= 6) { arr[n] = 10; n++; }

D. if (n < 5) { arr[n] = 10; n++; }

Solution

1. Step 1: Check array capacity before insertion

   Array size is 6, so insertion is safe only if n < 6.

2. Step 2: Insert element and update count

   If condition is true, assign arr[n] = 10 and increment n to reflect new size.

3. Final Answer:

   if (n < 6) { arr[n] = 10; n++; } -> Option A

4. Quick Check:

   Check capacity before insert, then add element [OK]

Hint: Always check n < array size before inserting [OK]

Common Mistakes:

• Not checking array size before insertion
• Using <= instead of < causing overflow
• Wrong size limit in condition