Array Insertion at Middle Index in DSA C - Time & Space Complexity

Time Complexity: Array Insertion at Middle Index

O(n)

Understanding Time Complexity

We want to understand how the time needed to insert an element in the middle of an array changes as the array grows.

Specifically, how does the work increase when the array size gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void insertMiddle(int arr[], int n, int x) {
    int mid = n / 2;
    for (int i = n; i > mid; i--) {
        arr[i] = arr[i - 1];
    }
    arr[mid] = x;
}
    

This code inserts a new element x into the middle of an array by shifting elements to the right.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that shifts elements one position to the right.
• How many times: Approximately n/2 times, where n is the current size of the array.

How Execution Grows With Input

As the array size grows, the number of elements to shift grows roughly half as fast.

Input Size (n)	Approx. Operations (shifts)
10	5
100	50
1000	500

Pattern observation: The number of operations grows linearly with the size of the array.

Final Time Complexity

Time Complexity: O(n)

This means the time to insert in the middle grows in direct proportion to the array size.

Common Mistake

[X] Wrong: "Inserting in the middle is always fast because we just put the element there."

[OK] Correct: We must move many elements to make space, which takes time proportional to the number of elements shifted.

Interview Connect

Understanding this helps you explain why arrays are not always the best choice for frequent middle insertions, showing your grasp of data structure trade-offs.

Self-Check

"What if we inserted at the end of the array instead? How would the time complexity change?"

Practice

1. What is the correct middle index to insert an element in an array of size 6?

easy

A. 5

B. 2

C. 4

D. 3

Solution

1. Step 1: Calculate middle index for even-sized array

   For an array of size 6, middle index is size/2 = 6/2 = 3.

2. Step 2: Confirm insertion position

   Inserting at index 3 places the element exactly in the middle.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Middle index = size/2 = 3 [OK]

Hint: Middle index = array size divided by 2 [OK]

Common Mistakes:

• Using size-1 as middle index
• Using size/2 - 1 for even size
• Confusing zero-based indexing

2. Which of the following C code snippets correctly inserts an element at the middle index of an array arr of size n?

easy

A. int mid = n / 2; for(int i = 0; i < mid; i++) arr[i] = arr[i+1]; arr[mid] = x;

B. int mid = n / 2; for(int i = n; i > mid; i--) arr[i] = arr[i-1]; arr[mid] = x;

C. int mid = n / 2; arr[mid] = x;

D. int mid = n / 2; for(int i = mid; i < n; i++) arr[i] = arr[i+1]; arr[mid] = x;

Solution

1. Step 1: Identify correct shifting direction

   To insert at middle, elements from middle to end must shift right to make space.

2. Step 2: Check code correctness

   int mid = n / 2; for(int i = n; i > mid; i--) arr[i] = arr[i-1]; arr[mid] = x; shifts elements right from end to middle, then inserts x at mid. Others shift incorrectly or overwrite.

3. Final Answer:

   int mid = n / 2; for(int i = n; i > mid; i--) arr[i] = arr[i-1]; arr[mid] = x; -> Option B

4. Quick Check:

   Shift right from end to mid, then insert [OK]

Hint: Shift elements right from end to middle before insertion [OK]

Common Mistakes:

• Shifting elements left instead of right
• Not shifting elements before insertion
• Overwriting elements without shifting

3. What will be the content of the array after inserting 99 at the middle index of arr = {10, 20, 30, 40, 50} using the correct insertion method?

medium

A. [10, 20, 30, 40, 99, 50]

B. [10, 20, 99, 30, 40, 50]

C. [10, 20, 30, 99, 40, 50]

D. [10, 20, 30, 40, 50, 99]

Solution

1. Step 1: Calculate middle index

   Array size is 5, middle index = 5/2 = 2 (integer division).

2. Step 2: Shift elements right and insert 99

   Shift elements from index 4 to 2 right by one position. Insert 99 at index 2.

3. Final Answer:

   [10, 20, 99, 30, 40, 50] -> Option C

4. Quick Check:

   Insert at index 2 shifts elements right [OK]

Hint: Middle index = size/2; shift right, then insert [OK]

Common Mistakes:

• Inserting at wrong index
• Not shifting elements before insertion
• Overwriting elements

4. Identify the error in the following code snippet that inserts an element x at the middle of array arr of size n:

int mid = n / 2;
for(int i = mid; i < n; i++) {
    arr[i+1] = arr[i];
}
arr[mid] = x;

medium

A. Loop should run backwards from n to mid

B. Index mid is incorrect for insertion

C. No need to shift elements before insertion

D. Array size n should be incremented before insertion

Solution

1. Step 1: Analyze loop direction

   The loop shifts elements from mid to n forward, but does so from low to high index, causing overwrite.

2. Step 2: Correct loop direction

   Loop must run backwards from n to mid to shift elements right safely without overwriting.

3. Final Answer:

   Loop should run backwards from n to mid -> Option A

4. Quick Check:

   Shift right must be done backwards [OK]

Hint: Shift elements right by looping backwards from end [OK]

Common Mistakes:

• Looping forward causing data overwrite
• Not updating array size after insertion
• Incorrect middle index calculation

5. Given an array arr = {5, 10, 15, 20, 25, 30} of size 6, write the final array after inserting 99 at the middle index and then inserting 77 at the new middle index of the updated array.

hard

A. [5, 10, 15, 77, 99, 20, 25, 30]

B. [5, 10, 77, 99, 15, 20, 25, 30]

C. [5, 10, 99, 15, 77, 20, 25, 30]

D. [5, 10, 15, 99, 77, 20, 25, 30]

Solution

1. Step 1: Insert 99 at middle of original array

   Original size = 6, middle index = 3. Insert 99 at index 3 shifting elements right: [5, 10, 15, 99, 20, 25, 30]

2. Step 2: Insert 77 at middle of updated array

   New size = 7, middle index = 7/2 = 3. Insert 77 at index 3 shifting elements right: [5, 10, 15, 77, 99, 20, 25, 30]

3. Final Answer:

   [5, 10, 15, 77, 99, 20, 25, 30] -> Option A

4. Quick Check:

   Insert twice at middle recalculating index each time [OK]

Hint: Recalculate middle after each insertion before next insert [OK]

Common Mistakes:

• Not recalculating middle index after first insertion
• Overwriting elements without shifting
• Inserting at wrong index second time