Array limitations in Go - Time & Space Complexity

Time Complexity: Array limitations

O(n)

Understanding Time Complexity

Arrays are simple and fast for storing items in order. But they have limits that affect how fast some actions run.

We want to see how these limits affect the time it takes to do common tasks with arrays.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

package main

func insertAtStart(arr []int, val int) []int {
    newArr := make([]int, len(arr)+1)
    newArr[0] = val
    for i := 0; i < len(arr); i++ {
        newArr[i+1] = arr[i]
    }
    return newArr
}

This code inserts a new value at the start of an array by creating a new array and copying all elements.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Copying each element from the old array to the new array.
• How many times: Once for every element in the original array (n times).

How Execution Grows With Input

As the array gets bigger, the time to copy all elements grows directly with its size.

Input Size (n)	Approx. Operations
10	About 10 copies
100	About 100 copies
1000	About 1000 copies

Pattern observation: The work grows in a straight line with the number of items.

Final Time Complexity

Time Complexity: O(n)

This means the time to insert at the start grows directly with the array size because all elements must be moved.

Common Mistake

[X] Wrong: "Inserting at the start of an array is always fast like adding at the end."

[OK] Correct: Adding at the start requires moving every element, so it takes more time as the array grows.

Interview Connect

Understanding array limits helps you explain why some operations are slower and when to choose other data structures.

Self-Check

"What if we used a linked list instead of an array for inserting at the start? How would the time complexity change?"