Common array operations - 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 complete operations changes as the array grows.

We want to understand how fast or slow common array tasks run when the array size increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Find the sum of all elements in an array
int sumArray(int arr[], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
    }
    return sum;
}
    

This code adds up every number in the array to find the total sum.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each element of the array once.
• How many times: Exactly n times, where n is the array size.

How Execution Grows With Input

As the array gets bigger, the number of additions grows directly with the size.

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

Pattern observation: The work grows in a straight line with the array size.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the sum grows directly in proportion to the number of elements.

Common Mistake

[X] Wrong: "Adding all elements is a constant time operation because it just adds numbers."

[OK] Correct: Even though adding two numbers is quick, you must add each element one by one, so the total time depends on how many elements there are.

Interview Connect

Understanding how array operations scale helps you explain your code choices clearly and shows you know how to handle data efficiently.

Self-Check

"What if we searched for a specific value instead of summing all elements? How would the time complexity 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 pointer to an integer

C. Declares a single integer variable

D. Creates a 2D array of integers

Solution

1. Step 1: Understand the declaration

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

2. Step 2: Check the initialization

   The array is initialized with values 1, 2, 3, 4, and 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 an array of 5 integers with values 1 to 5 [OK]

Hint: Array size and values match initialization count [OK]

Common Mistakes:

• Confusing array with pointer declaration
• Thinking it's a single variable, not an array
• Assuming it's a 2D array

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

easy

A. arr(3)

B. arr[2]

C. arr{3}

D. arr[3]

Solution

1. Step 1: Recall array indexing in C

   Arrays in C use zero-based indexing, so the first element is arr[0].

2. Step 2: Identify the third element index

   The third element is at index 2, so arr[2] accesses it.

3. Final Answer:

   arr[2] -> Option B

4. Quick Check:

   Third element index = 2 [OK]

Hint: Remember C arrays start at index 0 [OK]

Common Mistakes:

• Using parentheses instead of brackets
• Using 1-based indexing (arr[3])
• 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];
}
printf("%d", sum);

medium

A. 100

B. 90

C. Syntax error

D. 40

Solution

1. Step 1: Sum all elements in the array

   The loop adds arr[0]=10, arr[1]=20, arr[2]=30, arr[3]=40 to sum.

2. Step 2: Calculate the total sum

   10 + 20 + 30 + 40 = 100.

3. Final Answer:

   100 -> Option A

4. Quick Check:

   Sum of array elements = 100 [OK]

Hint: Add all elements using loop index 0 to size-1 [OK]

Common Mistakes:

• Off-by-one error in loop causing wrong sum
• Confusing sum with last element value
• Syntax errors from missing semicolons

4. Identify the error in this code snippet:

int arr[3] = {1, 2, 3};
for(int i = 0; i <= 3; i++) {
    printf("%d ", arr[i]);
}

medium

A. Array size should be 4

B. printf format specifier is wrong

C. Loop condition should be i < 3, not i <= 3

D. Variable i should be declared outside the loop

Solution

1. Step 1: Analyze loop condition

   The loop runs from i=0 to i=3 inclusive, so it accesses arr[3].

2. Step 2: Check array bounds

   Array arr has size 3, valid indices are 0,1,2. Accessing arr[3] causes out-of-bounds error.

3. Final Answer:

   Loop condition should be i < 3, not i <= 3 -> Option C

4. Quick Check:

   Array index must be less than size [OK]

Hint: Loop index must be less than array size [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Assuming array size auto-expands
• Misunderstanding printf format specifier

5. You want to find the largest number in an integer array arr of size n. Which code snippet correctly does this?

hard

A. int max = arr[n]; for(int i = 0; i < n; i++) { if(arr[i] > max) max = arr[i]; }

B. int max = 0; for(int i = 0; i <= n; i++) { if(arr[i] > max) max = arr[i]; }

C. int max = arr[0]; for(int i = 1; i < n; i++) { if(arr[i] < max) max = arr[i]; }

D. int max = arr[0]; for(int i = 1; i < n; i++) { if(arr[i] > max) max = arr[i]; }

Solution

1. Step 1: Initialize max with first element

   Set max = arr[0] to start comparison from first element.

2. Step 2: Loop from second element to end

   Loop i from 1 to n-1, compare arr[i] with max, update max if arr[i] is larger.

3. Step 3: Check other options for errors

   int max = 0; for(int i = 0; i <= n; i++) { if(arr[i] > max) max = arr[i]; } uses max=0 which fails if all numbers are negative; loop condition i <= n causes out-of-bounds; int max = arr[n]; for(int i = 0; i < n; i++) { if(arr[i] > max) max = arr[i]; } initializes max with arr[n] which is invalid index; int max = arr[0]; for(int i = 1; i < n; i++) { if(arr[i] < max) max = arr[i]; } finds minimum instead of maximum.

4. Final Answer:

   int max = arr[0]; for(int i = 1; i < n; i++) { if(arr[i] > max) max = arr[i]; } -> Option D

5. Quick Check:

   Initialize max with first element and compare correctly [OK]

Hint: Start max with arr[0], loop i from 1 to n-1 [OK]

Common Mistakes:

• Using wrong loop bounds causing out-of-bounds access
• Initializing max with 0 ignoring negative values
• Confusing max with min logic