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

Practice

1. What is the middle index of an array with 7 elements when inserting a new element?

easy

A. 3

B. 4

C. 2

D. 5

Solution

1. Step 1: Calculate middle index for odd length array

   For an array of length 7, middle index = length // 2 = 7 // 2 = 3.

2. Step 2: Understand insertion position

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

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Middle index = length // 2 = 3 [OK]

Hint: Middle index = length // 2 for insertion [OK]

Common Mistakes:

• Using length // 2 + 1 for middle index
• Using length // 2 - 1 for middle index
• Confusing middle index with last index

2. Which of the following Python statements correctly inserts the value 10 at the middle index of list arr = [1, 2, 3, 4]?

easy

A. arr.insert(0, 10)

B. arr.insert(len(arr), 10)

C. arr.insert(len(arr) // 2, 10)

D. arr.append(10)

Solution

1. Step 1: Calculate middle index for arr

   Length of arr is 4, middle index = 4 // 2 = 2.

2. Step 2: Use insert method at middle index

   arr.insert(2, 10) inserts 10 at index 2, which is the middle.

3. Final Answer:

   arr.insert(len(arr) // 2, 10) -> Option C

4. Quick Check:

   Use insert at middle index = len(arr)//2 [OK]

Hint: Use arr.insert(len(arr)//2, value) to insert in middle [OK]

Common Mistakes:

• Using append() which adds at end
• Using insert(len(arr), value) which adds at end
• Using insert(0, value) which adds at start

3. What will be the output of the following code?

arr = [5, 10, 15, 20]
mid = len(arr) // 2
arr.insert(mid, 12)
print(arr)

medium

A. [12, 5, 10, 15, 20]

B. [5, 10, 12, 15, 20]

C. [5, 10, 15, 12, 20]

D. [5, 10, 15, 20, 12]

Solution

1. Step 1: Calculate middle index

   Length of arr is 4, so mid = 4 // 2 = 2.

2. Step 2: Insert 12 at index 2

   arr.insert(2, 12) inserts 12 before element at index 2 (which is 15).

3. Final Answer:

   [5, 10, 12, 15, 20] -> Option B

4. Quick Check:

   Insert at mid index shifts elements right [OK]

Hint: Insert at mid index shifts elements right [OK]

Common Mistakes:

• Inserting at wrong index causing misplaced element
• Appending instead of inserting
• Confusing index with value

4. Find the error in the code below that tries to insert 99 in the middle of arr = [1, 2, 3, 4, 5]:

arr = [1, 2, 3, 4, 5]
mid = len(arr) / 2
arr.insert(mid, 99)
print(arr)

medium

A. Using '/' instead of '//' for middle index calculation

B. Using insert() instead of append() method

C. Not defining arr before insertion

D. Using print() incorrectly

Solution

1. Step 1: Check middle index calculation

   len(arr) / 2 returns a float (2.5), but insert() requires an integer index.

2. Step 2: Correct middle index calculation

   Use integer division '//' to get integer index: mid = len(arr) // 2 = 2.

3. Final Answer:

   Using '/' instead of '//' for middle index calculation -> Option A

4. Quick Check:

   Index must be int, use '//' not '/' [OK]

Hint: Use '//' for integer division to get valid index [OK]

Common Mistakes:

• Using '/' causing TypeError
• Forgetting to calculate middle index
• Using append() instead of insert()

5. Given arr = [2, 4, 6, 8, 10, 12], write code to insert the value 7 exactly in the middle so that the array remains sorted. What will be the final array?

hard

A. [2, 4, 7, 6, 8, 10, 12]

B. [2, 4, 6, 8, 7, 10, 12]

C. [7, 2, 4, 6, 8, 10, 12]

D. [2, 4, 6, 7, 8, 10, 12]

Solution

1. Step 1: Calculate middle index for even length array

   Length is 6, middle index = 6 // 2 = 3.

2. Step 2: Insert 7 at index 3 to keep array sorted

   Inserting 7 at index 3 places it between 6 and 8, maintaining sorted order.

3. Final Answer:

   [2, 4, 6, 7, 8, 10, 12] -> Option D

4. Quick Check:

   Insert 7 at middle index 3 to keep sorted [OK]

Hint: Insert at middle index to keep sorted order [OK]

Common Mistakes:

• Inserting 7 at wrong index breaking order
• Appending 7 at end
• Inserting 7 at start