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

Practice

1. What does the following C++ code do?
int arr[5] = {1, 2, 3, 4, 5};

easy

A. Creates an array of 5 integers with values 1 to 5

B. Creates a vector of 5 integers with values 1 to 5

C. Creates a pointer to an integer array

D. Declares an uninitialized array of size 5

Solution

1. Step 1: Understand array declaration

   The code declares an integer array named arr with size 5.

2. Step 2: Check initialization

   The array is initialized with values 1, 2, 3, 4, 5 in order.

3. Final Answer:

   Creates an array of 5 integers with values 1 to 5 -> Option A

4. Quick Check:

   Array declaration with initialization = Creates array with values [OK]

Hint: Array size and values in braces means initialized array [OK]

Common Mistakes:

• Confusing array with vector
• Thinking it's a pointer declaration
• Assuming array is uninitialized

2. Which of the following is the correct syntax to access the third element of an array named arr in C++?

easy

A. arr[3];

B. arr(3);

C. arr{3};

D. arr[2];

Solution

1. Step 1: Recall zero-based indexing

   Arrays in C++ start at index 0, so the third element is at index 2.

2. Step 2: Identify correct syntax for access

   Array elements are accessed using square brackets, so arr[2] is correct.

3. Final Answer:

   arr[2]; -> Option D

4. Quick Check:

   Third element index = 2, use square brackets [OK]

Hint: Remember arrays start at 0, so third element is index 2 [OK]

Common Mistakes:

• Using parentheses instead of brackets
• Using 1-based indexing
• Using curly braces for access

3. What is the output of this C++ code?

int arr[4] = {10, 20, 30, 40};
int sum = 0;
for(int i = 0; i < 4; i++) {
    sum += arr[i];
}
std::cout << sum;

medium

A. 100

B. 90

C. 40

D. 10

Solution

1. Step 1: Identify array elements and loop

   The array has elements 10, 20, 30, 40 and the loop runs from i=0 to 3.

2. Step 2: Calculate sum of elements

   sum = 10 + 20 + 30 + 40 = 100

3. Final Answer:

   100 -> Option A

4. Quick Check:

   Sum of all elements = 100 [OK]

Hint: Add all elements in loop to get sum [OK]

Common Mistakes:

• Stopping loop early
• Using wrong indices
• Printing sum before loop

4. Find the error in this C++ code that tries to print all elements of an array:

int arr[3] = {5, 10, 15};
for(int i = 1; i <= 3; i++) {
    std::cout << arr[i] << " ";
}

medium

A. Loop index starts at 1 instead of 0

B. Array size is incorrect

C. Using <= causes out-of-bounds access

D. Missing semicolon after cout statement

Solution

1. Step 1: Analyze loop indices

   The loop runs i from 1 to 3 inclusive, so i=3 is included.

2. Step 2: Check array bounds

   Array indices are 0,1,2. Accessing arr[3] is out-of-bounds and causes error.

3. Final Answer:

   Using <= causes out-of-bounds access -> Option C

4. Quick Check:

   Loop must use i < size, not <= [OK]

Hint: Use i < size, not i <= size in loops [OK]

Common Mistakes:

• Starting loop at 1 instead of 0 (not error but unusual)
• Ignoring out-of-bounds access
• Assuming array size is wrong

5. You have an array int arr[6] = {2, 4, 6, 8, 10, 12};. How do you update the element with value 8 to 9 using a loop?

hard

A. arr[3] = 9;

B. for(int i=0; i<6; i++) { if(arr[i] == 8) arr[i] = 9; }

C. for(int i=1; i<=6; i++) { if(arr[i] == 8) arr[i] = 9; }

D. arr[4] = 9;

Solution

1. Step 1: Understand the problem

   We want to find the element with value 8 and update it to 9 using a loop.

2. Step 2: Check loop and condition

   Loop from i=0 to 5 checks each element; if arr[i] == 8, assign arr[i] = 9.

3. Final Answer:

   for(int i=0; i<6; i++) { if(arr[i] == 8) arr[i] = 9; } -> Option B

4. Quick Check:

   Loop with condition to find and update element [OK]

Hint: Loop through array, check value, then update [OK]

Common Mistakes:

• Using wrong indices in loop
• Assigning wrong array index
• Not using loop to find value