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

Time Complexity: Array Insertion at Middle Index

O(n)

Understanding Time Complexity

We want to understand how long it takes to insert an element in the middle of an array.

How does the time needed change as the array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn insert_middle(arr: &mut Vec<i32>, value: i32) {
    let mid = arr.len() / 2;
    arr.insert(mid, value);
}

This code inserts a value exactly in the middle of a dynamic array (vector).

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Shifting elements to the right to make space for the new element.
• How many times: About half of the array elements are moved one step to the right.

How Execution Grows With Input

When the array size grows, the number of elements to shift grows roughly in the same way.

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

Pattern observation: The number of operations grows roughly in direct proportion to the size of the array.

Final Time Complexity

Time Complexity: O(n)

This means the time to insert in the middle grows linearly as the array gets bigger.

Common Mistake

[X] Wrong: "Inserting in the middle is always fast because we just add one element."

[OK] Correct: Actually, many elements need to move to make space, so the work grows with array size.

Interview Connect

Knowing how array insertions work helps you choose the right data structure and explain your choices clearly.

Self-Check

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

Practice

1. What does inserting an element at the middle index of an array mean?

easy

A. Adding a new element at the end of the array

B. Replacing the middle element with a new one

C. Adding a new element exactly in the center, shifting others right

D. Removing the middle element from the array

Solution

1. Step 1: Understand middle index insertion

   Inserting at the middle means placing a new element at the center position, pushing existing elements to the right.

2. Step 2: Differentiate from other operations

   Replacing or removing elements changes existing data, but insertion adds a new element without deletion.

3. Final Answer:

   Adding a new element exactly in the center, shifting others right -> Option C

4. Quick Check:

   Middle insertion means add and shift [OK]

Hint: Middle insertion adds element, shifts others right [OK]

Common Mistakes:

• Thinking insertion replaces an element
• Confusing insertion with removal
• Assuming insertion always happens at end

2. Which Rust code correctly inserts the value 99 at the middle index of a vector named vec?

easy

A. vec.insert(vec.len() / 2, 99);

B. vec.push(99);

C. vec[vec.len() / 2] = 99;

D. vec.remove(vec.len() / 2); vec.push(99);

Solution

1. Step 1: Identify correct insertion method

   Rust's insert method adds an element at a given index, shifting others right.

2. Step 2: Calculate middle index and apply insert

   Using vec.len() / 2 gives the middle index; vec.insert places 99 there correctly.

3. Final Answer:

   vec.insert(vec.len() / 2, 99); -> Option A

4. Quick Check:

   Use insert with middle index [OK]

Hint: Use vec.insert(middle_index, value) to insert [OK]

Common Mistakes:

• Using push adds at end, not middle
• Assigning with vec[index] replaces, not inserts
• Removing then pushing changes order

3. What is the output of this Rust code?

let mut vec = vec![10, 20, 30, 40];
vec.insert(vec.len() / 2, 25);
println!("{:?}", vec);

medium

A. [10, 20, 30, 25, 40]

B. [10, 20, 25, 30, 40]

C. [10, 25, 20, 30, 40]

D. [25, 10, 20, 30, 40]

Solution

1. Step 1: Calculate middle index

   Vector length is 4, so middle index is 4 / 2 = 2.

2. Step 2: Insert 25 at index 2

   Inserting 25 at index 2 shifts elements at and after index 2 right: 30 and 40 move right.

3. Final Answer:

   [10, 20, 25, 30, 40] -> Option B

4. Quick Check:

   Insert at middle shifts elements right [OK]

Hint: Middle index = length/2; insert shifts right [OK]

Common Mistakes:

• Inserting at wrong index
• Confusing insert with replace
• Miscounting vector length

4. Identify the error in this Rust code that tries to insert 50 at the middle of vec:

let mut vec = vec![1, 2, 3, 4, 5];
let mid = vec.len() / 2;
vec[mid] = 50;
println!("{:?}", vec);

medium

A. Using assignment replaces element instead of inserting

B. vec.len() / 2 is incorrect middle index

C. vec is immutable, cannot modify

D. println! syntax is wrong

Solution

1. Step 1: Understand vec[mid] = 50;

   This replaces the element at index mid instead of inserting a new one.

2. Step 2: Correct method is insert

   To insert, use vec.insert(mid, 50); which shifts elements right.

3. Final Answer:

   Using assignment replaces element instead of inserting -> Option A

4. Quick Check:

   Assignment replaces, insert adds [OK]

Hint: Use insert() to add, not assignment [OK]

Common Mistakes:

• Replacing element instead of inserting
• Misunderstanding vector mutability
• Incorrect println! usage

5. Given a vector vec = vec![5, 10, 15, 20, 25, 30], write Rust code to insert 17 exactly in the middle so that the vector remains sorted. What will be the vector after insertion?

hard

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

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

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

D. [5, 10, 15, 17, 20, 25, 30]

Solution

1. Step 1: Find middle index for insertion

   Vector length is 6, middle index is 6 / 2 = 3.

2. Step 2: Insert 17 at index 3 to keep sorted order

   Inserting 17 at index 3 shifts elements 20, 25, 30 right, keeping order.

3. Final Answer:

   [5, 10, 15, 17, 20, 25, 30] -> Option D

4. Quick Check:

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

Hint: Insert at length/2 to keep sorted vector [OK]

Common Mistakes:

• Inserting at wrong index breaking order
• Appending instead of inserting
• Replacing element instead of inserting