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