Array traversal in C++ - Time & Space Complexity

Time Complexity: Array traversal

O(n)

Understanding Time Complexity

When we go through each item in an array one by one, we want to know how the time it takes grows as the array gets bigger.

We ask: How does the work increase when the array size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}
    

This code goes through each element of the array and prints it out once.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Accessing and printing each element of the array.
• How many times: Exactly once for each of the n elements in the array.

How Execution Grows With Input

As the array gets bigger, the number of steps grows directly with the number of elements.

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

Pattern observation: Doubling the array size doubles the work needed.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line with the number of items in the array.

Common Mistake

[X] Wrong: "Since the loop is simple, it must be constant time O(1)."

[OK] Correct: Even a simple loop that touches every element depends on how many elements there are, so time grows with n, not fixed.

Interview Connect

Understanding how simple loops scale helps you explain and improve code efficiency in many real tasks.

Self-Check

"What if we nested another loop inside to compare every element with every other? How would the time complexity change?"

Practice

1. What does array traversal mean in C++ programming?

easy

A. Visiting each element of the array one by one

B. Creating a new array with the same elements

C. Sorting the array elements in order

D. Deleting elements from the array

Solution

1. Step 1: Understand the term 'array traversal'

   Array traversal means going through each element in the array in sequence.

2. Step 2: Match the definition to the options

   Visiting each element of the array one by one correctly describes visiting each element one by one.

3. Final Answer:

   Visiting each element of the array one by one -> Option A

4. Quick Check:

   Array traversal = visiting elements in order [OK]

Hint: Traversal means visiting all elements one by one [OK]

Common Mistakes:

• Confusing traversal with sorting
• Thinking traversal means deleting elements
• Mixing traversal with copying arrays

2. Which of the following is the correct syntax to traverse an array arr of size n in C++?

easy

A. for(int i = 1; i <= n; i++) { /* access arr[i] */ }

B. for(int i = n; i > 0; i--) { /* access arr[i] */ }

C. for(int i = 0; i <= n; i++) { /* access arr[i] */ }

D. for(int i = 0; i < n; i++) { /* access arr[i] */ }

Solution

1. Step 1: Identify valid index range for array traversal

   Array indices in C++ start at 0 and go up to n-1, so loop should run from 0 to less than n.

2. Step 2: Check each option's loop condition

   for(int i = 0; i < n; i++) { /* access arr[i] */ } uses i from 0 to i < n, which is correct. Others either start at 1 or go out of bounds.

3. Final Answer:

   for(int i = 0; i < n; i++) { /* access arr[i] */ } -> Option D

4. Quick Check:

   Loop from 0 to n-1 = correct traversal [OK]

Hint: Array indices start at 0, loop till less than size [OK]

Common Mistakes:

• Starting loop at 1 instead of 0
• Using <= n causing out-of-bounds access
• Decrementing loop without correct index

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

int arr[] = {2, 4, 6};
for(int i = 0; i < 3; i++) {
    std::cout << arr[i] << " ";
}

medium

A. 0 2 4 6

B. 2 4 6 0

C. 2 4 6

D. 6 4 2

Solution

1. Step 1: Understand the loop and array elements

   The array has elements 2, 4, 6 at indices 0, 1, 2. The loop runs from i=0 to i=2.

2. Step 2: Print elements in order

   Each iteration prints arr[i] followed by a space: 2, then 4, then 6.

3. Final Answer:

   2 4 6 -> Option C

4. Quick Check:

   Print elements in order = 2 4 6 [OK]

Hint: Loop prints elements in order from index 0 to 2 [OK]

Common Mistakes:

• Expecting extra zero at end
• Printing elements in reverse order
• Confusing array indices with values

4. Identify the error in this C++ code snippet for array traversal:

int arr[4] = {1, 2, 3, 4};
for(int i = 0; i <= 4; i++) {
    std::cout << arr[i] << " ";
}

medium

A. Loop condition should be i < 4, not i <= 4

B. Array size should be 5 instead of 4

C. Loop variable i should start from 1

D. No error, code is correct

Solution

1. Step 1: Check loop condition against array size

   The array has size 4, valid indices are 0 to 3. Loop runs while i <= 4, which includes i=4 (out of bounds).

2. Step 2: Correct the loop condition

   Change condition to i < 4 to avoid accessing arr[4] which is invalid.

3. Final Answer:

   Loop condition should be i < 4, not i <= 4 -> Option A

4. Quick Check:

   Loop must stay within 0 to size-1 [OK]

Hint: Loop index must be less than array size, not less or equal [OK]

Common Mistakes:

• Using <= instead of < causing out-of-bounds
• Starting loop at 1 instead of 0
• Increasing array size unnecessarily

5. Given an integer array arr of size n, which code snippet correctly calculates the sum of all elements using array traversal?

hard

A. int sum = arr[0];
for(int i = 1; i <= n; i++) {
sum += arr[i];
}

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

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

D. int sum = 0;
for(int i = 0; i <= n; i++) {
sum += arr[i];
}

Solution

1. Step 1: Initialize sum and loop correctly

   Sum should start at 0. Loop must run from i=0 to i < n to include all elements.

2. Step 2: Check each option for correctness

   int sum = 0; for(int i = 0; i < n; i++) { sum += arr[i]; } initializes sum to 0 and loops correctly. Others either start sum wrong or loop out of bounds.

3. Final Answer:

   int sum = 0; for(int i = 0; i < n; i++) { sum += arr[i]; } -> Option B

4. Quick Check:

   Sum all elements from index 0 to n-1 [OK]

Hint: Start sum at 0 and loop from 0 to less than n [OK]

Common Mistakes:

• Starting sum with arr[0] and looping incorrectly
• Looping with i <= n causing out-of-bounds
• Skipping first element by starting at i=1