Insert at Middle Specific Position in DSA Python - Time & Space Complexity

Time Complexity: Insert at Middle Specific Position

O(n)

Understanding Time Complexity

When we insert an element at a specific middle position in a list, we want to know how the time to do this changes as the list grows.

We ask: How much work does it take to insert in the middle as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def insert_at_middle(arr, pos, value):
    arr.append(value)
    for i in range(len(arr) - 1, pos, -1):
        arr[i] = arr[i - 1]
    arr[pos] = value

# Example usage:
arr = [1, 2, 4, 5]
insert_at_middle(arr, 2, 3)  # Insert 3 at index 2

This code inserts a value at a given middle position by shifting elements to the right.

Identify Repeating Operations

• Primary operation: The for-loop shifts elements one by one to the right.
• How many times: It runs from the end of the list down to the insertion position, so roughly n - pos times.

How Execution Grows With Input

As the list gets bigger, the number of elements to shift grows roughly with the size of the list.

Input Size (n)	Approx. Operations (shifts)
10	About 5 shifts if inserting in the middle
100	About 50 shifts
1000	About 500 shifts

Pattern observation: The work grows roughly in direct proportion to the size of the list.

Final Time Complexity

Time Complexity: O(n)

This means the time to insert grows linearly with the list size because we must shift many elements.

Common Mistake

[X] Wrong: "Inserting in the middle is always fast and takes constant time."

[OK] Correct: Because we must move all elements after the insertion point, the time grows with the number of elements shifted, not constant.

Interview Connect

Understanding how insertion time grows helps you explain trade-offs in data structures and shows you can analyze real code performance clearly.

Self-Check

"What if we changed the data structure to a linked list? How would the time complexity of inserting at a middle position change?"