One-dimensional arrays in C++ - Time & Space Complexity

Time Complexity: One-dimensional arrays

O(n)

Understanding Time Complexity

When working with one-dimensional arrays, it's important to understand how the time to process them grows as the array gets bigger.

We want to know how the number of steps changes when the array size increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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 all the numbers in a one-dimensional array of size n.

Identify Repeating Operations

• Primary operation: Adding each element of the array to the sum.
• How many times: Exactly once for each element, so n times.

How Execution Grows With Input

As the array gets bigger, the number of additions grows in a straight line with the size.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to sum the array grows directly with the number of elements.

Common Mistake

[X] Wrong: "The loop runs faster because it just adds numbers, so time doesn't grow much with size."

[OK] Correct: Even simple steps add up; more elements mean more additions, so time grows with n.

Interview Connect

Understanding how loops over arrays scale is a key skill that helps you reason about many real-world problems and algorithms.

Self-Check

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

Practice

1. What is the starting index of a one-dimensional array in C++?

easy

A. -1

B. 1

C. 0

D. Depends on the array size

Solution

1. Step 1: Understand array indexing in C++

   Arrays in C++ always start indexing from 0, meaning the first element is at index 0.

2. Step 2: Confirm the index range

   Indexes go from 0 up to size-1, so the first index is always 0 regardless of array size.

3. Final Answer:

   0 -> Option C

4. Quick Check:

   Array indexing starts at 0 [OK]

Hint: Remember: C++ arrays always start at zero index [OK]

Common Mistakes:

• Thinking arrays start at 1
• Assuming negative indexes are valid
• Confusing with other languages

2. Which of the following is the correct way to declare an integer array of size 5 in C++?

easy

A. array<int> arr(5);

B. int arr(5);

C. int arr = new int[5];

D. int arr[5];

Solution

1. Step 1: Recall C++ array declaration syntax

   In C++, a fixed-size array is declared using square brackets with size: int arr[5];

2. Step 2: Check other options for correctness

   int arr(5); uses parentheses which is invalid for arrays. array<int> arr(5); uses incorrect syntax (not standard array). int arr = new int[5]; uses dynamic allocation syntax but is incorrect without pointer.

3. Final Answer:

   int arr[5]; -> Option D

4. Quick Check:

   Fixed-size arrays use square brackets [OK]

Hint: Use square brackets [] to declare fixed-size arrays [OK]

Common Mistakes:

• Using parentheses instead of brackets
• Confusing with vector syntax
• Incorrect dynamic allocation syntax

3. What will be the output of the following code?

int arr[4] = {10, 20, 30, 40};
std::cout << arr[2];

medium

A. 30

B. 20

C. 40

D. Compilation error

Solution

1. Step 1: Identify the array elements and indexes

   The array arr has elements: arr[0]=10, arr[1]=20, arr[2]=30, arr[3]=40.

2. Step 2: Access the element at index 2

   arr[2] is 30, so std::cout will print 30.

3. Final Answer:

   30 -> Option A

4. Quick Check:

   arr[2] = 30 [OK]

Hint: Remember array index starts at 0, so arr[2] is third element [OK]

Common Mistakes:

• Confusing index 2 with 1 or 3
• Expecting output 20 or 40
• Thinking code causes error

4. Identify the error in the following code snippet:

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

medium

A. Missing semicolon after array declaration

B. Loop runs one time too many, causing out-of-bounds access

C. Syntax error in for loop declaration

D. Array size is incorrect, should be 4

Solution

1. Step 1: Analyze the loop range and array size

   The array has size 3 with valid indexes 0,1,2. The loop runs from i=0 to i=3 inclusive, which means 4 iterations.

2. Step 2: Identify out-of-bounds access

   When i=3, arr[3] is accessed, which is outside the array bounds and causes undefined behavior.

3. Final Answer:

   Loop runs one time too many, causing out-of-bounds access -> Option B

4. Quick Check:

   Loop index must be less than array size [OK]

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

Common Mistakes:

• Using <= instead of <
• Assuming array size is 4
• Ignoring out-of-bounds errors

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

hard

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

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

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

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

Solution

1. Step 1: Understand correct loop bounds for array traversal

   Array indexes go from 0 to n-1, so loop must run i from 0 to less than n.

2. Step 2: Check each option for correctness

   int sum = 0; for(int i = 1; i < n; i++) sum += arr[i]; starts from 1, missing arr[0]. int sum = 0; for(int i = 0; i <= n; i++) sum += arr[i]; uses <= n, causing out-of-bounds access. int sum = 0; for(int i = 0; i < n; i++) sum += arr[i]; correctly sums all elements from 0 to n-1. int sum = arr[0]; for(int i = 1; i < n; i++) sum = arr[i]; overwrites sum instead of adding.

3. Final Answer:

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

4. Quick Check:

   Loop from 0 to n-1 sums all elements [OK]

Hint: Loop from 0 to less than n to cover all elements [OK]

Common Mistakes:

• Starting loop at 1
• Using <= n causing errors
• Overwriting sum instead of adding