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

Time Complexity: Array Deletion at Middle Index

O(n)

Understanding Time Complexity

When we delete an element from the middle of an array, the time it takes depends on how many elements need to move.

We want to know how the work grows as the array gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void deleteMiddle(int arr[], int *size, int mid) {
    for (int i = mid; i < *size - 1; i++) {
        arr[i] = arr[i + 1];
    }
    (*size)--;
}
    

This code deletes the element at the middle index by shifting all elements after it one step left.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop shifting elements left after the middle index.
• How many times: It runs from the middle index to the end of the array, about half the array size.

How Execution Grows With Input

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

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to delete grows in a straight line as the array gets bigger.

Common Mistake

[X] Wrong: "Deleting an element from the middle of an array is always fast and constant time."

[OK] Correct: Because after deletion, all elements after the deleted one must move, which takes time proportional to how many elements are after it.

Interview Connect

Understanding how array operations scale helps you explain trade-offs between arrays and other data structures like linked lists.

Self-Check

"What if we delete the first element instead of the middle? How would the time complexity change?"