Pointers and arrays in C - Time & Space Complexity

Time Complexity: Pointers and arrays

O(n)

Understanding Time Complexity

When working with pointers and arrays, it is important to understand how the program's running time changes as the size of the array grows.

We want to know how many steps the program takes when it accesses or processes array elements using pointers.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code prints each element of an integer array using a pointer to access elements.

Identify Repeating Operations

• Primary operation: Accessing each array element through pointer arithmetic inside the loop.
• How many times: The loop runs exactly size times, once for each element.

How Execution Grows With Input

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

Input Size (n)	Approx. Operations
10	About 10 pointer accesses and prints
100	About 100 pointer accesses and prints
1000	About 1000 pointer accesses and prints

Pattern observation: The work grows evenly as the array gets bigger, doubling the size doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the code grows directly in proportion to the number of elements in the array.

Common Mistake

[X] Wrong: "Using pointers makes accessing array elements faster and changes the time complexity."

[OK] Correct: Pointer access and array indexing both take constant time per element, so the overall time still grows linearly with the array size.

Interview Connect

Understanding how pointer and array access scales helps you explain memory handling and performance clearly in interviews.

Self-Check

"What if we used nested loops to process a 2D array with pointers? How would the time complexity change?"