Array Insertion at Beginning in DSA C - Time & Space Complexity

Time Complexity: Array Insertion at Beginning

O(n)

Understanding Time Complexity

We want to understand how long it takes to add a new item at the start of an array.

Specifically, how the time grows as the array gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void insertAtBeginning(int arr[], int *size, int capacity, int value) {
    if (*size >= capacity) return; // no space
    for (int i = *size; i > 0; i--) {
        arr[i] = arr[i - 1];
    }
    arr[0] = value;
    (*size)++;
}
    

This code inserts a new value at the start of the array by shifting all existing elements one step to the right.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that shifts elements to the right.
• How many times: It runs once for each existing element in the array (size times).

How Execution Grows With Input

As the array size grows, the number of shifts grows the same way.

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

Pattern observation: The work grows directly with the number of elements; doubling the array size doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to insert at the beginning grows linearly with the array size.

Common Mistake

[X] Wrong: "Inserting at the beginning is always fast because it's just one step."

[OK] Correct: Because all existing elements must move one step to make space, so the time depends on how many elements there are.

Interview Connect

Understanding this helps you explain why arrays are not always the best choice for adding items at the start, showing your grasp of data structure trade-offs.

Self-Check

"What if we changed the array to a linked list? How would the time complexity of insertion at the beginning change?"