Pointer arithmetic - Time & Space Complexity

Time Complexity: Pointer arithmetic

O(n)

Understanding Time Complexity

We want to see how the time to run code with pointer arithmetic changes as the input size grows.

How does moving pointers through an array affect the number of steps the program takes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code prints each element of an integer array using pointer arithmetic to move through the array.

Identify Repeating Operations

• Primary operation: Loop that moves the pointer and prints each element.
• How many times: Exactly once for each element in the array, so n times.

How Execution Grows With Input

Each element causes one print and one pointer move, so the steps grow directly with the number of elements.

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

Pattern observation: The work grows evenly as the input size grows; doubling the input doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the code grows in a straight line with the number of elements.

Common Mistake

[X] Wrong: "Pointer arithmetic makes the code run faster, so time complexity is less than O(n)."

[OK] Correct: Pointer arithmetic is just a way to access elements; it does not reduce the number of steps needed to process each element.

Interview Connect

Understanding how pointer arithmetic affects time helps you explain how low-level code works efficiently, a useful skill in many programming tasks.

Self-Check

"What if we replaced the for loop with a while loop that stops when the pointer reaches the end? How would the time complexity change?"