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

Time Complexity: Array Insertion at Middle Index

O(n)

Understanding Time Complexity

When we insert an element in 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.

def insert_middle(arr, value):
    mid = len(arr) // 2
    arr.append(0)  # Increase size by one
    for i in range(len(arr) - 1, mid, -1):
        arr[i] = arr[i - 1]
    arr[mid] = value

# Example: arr = [1, 2, 3, 4]

This code inserts a new value exactly in the middle of the 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: It runs roughly half the length of the array (from the end to the middle + 1).

How Execution Grows With Input

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

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to insert grows directly with the number of elements in the array.

Common Mistake

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

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

Interview Connect

Understanding how array insertions work helps you explain why some data structures are better for certain tasks.

Self-Check

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