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