Common array operations in C++ - Time & Space Complexity

Time Complexity: Common array operations

O(n)

Understanding Time Complexity

When working with arrays, it is important to know how the time to do common tasks changes as the array gets bigger.

We want to understand how fast operations like searching, inserting, or deleting run as the array size grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Find if a value exists in the array
bool contains(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return true;
        }
    }
    return false;
}

// Insert a value at the end of the array
void insert(int arr[], int &n, int value, int capacity) {
    if (n < capacity) {
        arr[n] = value;
        n++;
    }
}

// Delete a value by shifting elements
void deleteValue(int arr[], int &n, int target) {
    int i = 0;
    while (i < n) {
        if (arr[i] == target) {
            for (int j = i; j < n - 1; j++) {
                arr[j] = arr[j + 1];
            }
            n--;
        } else {
            i++;
        }
    }
}
    

This code shows three common array operations: searching for a value, inserting at the end, and deleting a value by shifting elements.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through the array elements.
• How many times: For searching, up to n times; for deleting, nested loops cause up to n² in worst case; for inserting, constant time if space available.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations
10	Search: up to 10 checks; Insert: 1 step; Delete: up to 100 shifts
100	Search: up to 100 checks; Insert: 1 step; Delete: up to 10,000 shifts
1000	Search: up to 1000 checks; Insert: 1 step; Delete: up to 1,000,000 shifts

Pattern observation: Searching grows linearly with n, inserting stays constant, deleting can grow quadratically in worst case.

Final Time Complexity

Time Complexity: O(n) for search, O(1) for insert, O(n^2) for delete in worst case

This means searching takes time proportional to the array size, inserting takes constant time, but deleting can take much longer if many elements must be shifted.

Common Mistake

[X] Wrong: "Deleting an element from an array is always fast like inserting at the end."

[OK] Correct: Deleting requires shifting elements to fill the gap, which can take much more time as the array grows.

Interview Connect

Understanding these basic array operation costs helps you explain your choices clearly and shows you know how data size affects performance.

Self-Check

"What if we used a linked list instead of an array? How would the time complexity of delete change?"