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 is 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.

    void printArray(int arr[], int n) {
        for (int i = 0; i < n; i++) {
            printf("%d\n", arr[i]);
        }
    }
    

This code prints each element of a one-dimensional array of size n.

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 element, so n times.

How Execution Grows With Input

As the array size grows, the number of steps grows in a straight line.

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

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

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Accessing an array element takes more time as the array grows."

[OK] Correct: Each element access is done in constant time, no matter the array size. The total time grows only because there are more elements to access.

Interview Connect

Understanding how simple loops over arrays scale is a key skill. It helps you explain and reason about code efficiency clearly and confidently.

Self-Check

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

Practice

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

easy

A. 0

B. 1

C. -1

D. Depends on the array size

Solution

1. Step 1: Understand array indexing in C

   In C, arrays always start indexing from 0, meaning the first element is at index 0.

2. Step 2: Confirm the starting index

   This is a fixed rule in C and does not depend on array size or other factors.

3. Final Answer:

   0 -> Option A

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 like in some other languages
• Assuming negative indexes are valid
• Believing index depends on array size

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

easy

A. int arr = 5;

B. int arr();

C. array int arr[5];

D. int arr[5];

Solution

1. Step 1: Recall C array declaration syntax

   In C, arrays are declared by specifying the type, name, and size in square brackets, like int arr[5];

2. Step 2: Check each option

   int arr[5]; matches the correct syntax. int arr(); uses parentheses which is for functions. int arr = 5; assigns a single int, not an array. array int arr[5]; uses invalid keyword 'array'.

3. Final Answer:

   int arr[5]; -> Option D

4. Quick Check:

   Array declaration uses square brackets [OK]

Hint: Use square brackets for array size in declaration [OK]

Common Mistakes:

• Using parentheses instead of square brackets
• Assigning a single value instead of declaring array
• Using invalid keywords like 'array'

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

int arr[3] = {10, 20, 30};
printf("%d", arr[1]);

medium

A. 10

B. 30

C. 20

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.

2. Step 2: Understand the printf statement

   printf prints the value at arr[1], which is 20.

3. Final Answer:

   20 -> Option C

4. Quick Check:

   arr[1] = 20 [OK]

Hint: Remember array index 1 is second element [OK]

Common Mistakes:

• Confusing index 1 with index 0
• Expecting output 10 or 30 incorrectly
• Thinking code causes compilation error

4. Find the error in this code snippet:

int arr[4];
arr[4] = 10;

medium

A. Array index out of bounds

B. Missing semicolon

C. Wrong data type

D. No error

Solution

1. Step 1: Check array size and indexing

   The array arr has size 4, so valid indexes are 0,1,2,3 only.

2. Step 2: Identify the invalid index usage

   arr[4] accesses the fifth element, which is outside the array bounds causing undefined behavior.

3. Final Answer:

   Array index out of bounds -> Option A

4. Quick Check:

   Index must be less than array size [OK]

Hint: Index must be less than array size [OK]

Common Mistakes:

• Using index equal to array size
• Ignoring zero-based indexing
• Assuming no error for out-of-bounds access

5. Given the array declaration int nums[5] = {1, 2, 3, 4, 5};, which code snippet correctly calculates the sum of all elements?

hard

A. int sum = 0;
for(int i = 0; i <= 5; i++) sum += nums[i];

B. int sum = 0;
for(int i = 0; i < 5; i++) sum += nums[i];

C. int sum = 0;
for(int i = 1; i < 5; i++) sum += nums[i];

D. int sum = 0;
for(int i = 0; i < 4; i++) sum += nums[i];

Solution

1. Step 1: Understand array size and valid indexes

   The array nums has 5 elements with indexes 0 to 4.

2. Step 2: Analyze each loop condition

   int sum = 0; for(int i = 0; i <= 5; i++) sum += nums[i]; uses i <= 5 which accesses nums[5] (out of bounds). int sum = 0; for(int i = 0; i < 5; i++) sum += nums[i]; uses i < 5 which correctly iterates from 0 to 4. int sum = 0; for(int i = 1; i < 5; i++) sum += nums[i]; starts at 1, missing nums[0]. int sum = 0; for(int i = 0; i < 4; i++) sum += nums[i]; stops at 4, missing nums[4].

3. Final Answer:

   int sum = 0; for(int i = 0; i < 5; i++) sum += nums[i]; -> Option B

4. Quick Check:

   Loop from 0 to less than size sums all elements [OK]

Hint: Loop from 0 to less than array size for all elements [OK]

Common Mistakes:

• Using <= size causing out-of-bounds access
• Starting loop at 1 missing first element
• Stopping loop early missing last element