Pointer arithmetic in C++ - Time & Space Complexity

Time Complexity: Pointer arithmetic

O(n)

Understanding Time Complexity

Let's see how the time needed changes when we use pointer arithmetic in C++.

We want to know how the number of steps grows as we move through memory with pointers.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int sumArray(int* arr, int size) {
    int sum = 0;
    int* ptr = arr;
    for (int i = 0; i < size; i++) {
        sum += *ptr;
        ptr++;
    }
    return sum;
}
    

This code adds up all numbers in an array using a pointer that moves through the array.

Identify Repeating Operations

Look for loops or repeated steps.

• Primary operation: The for-loop that moves the pointer and adds values.
• How many times: Exactly once for each element in the array (size times).

How Execution Grows With Input

As the array gets bigger, the loop runs more times, adding each number.

Input Size (n)	Approx. Operations
10	About 10 additions and pointer moves
100	About 100 additions and pointer moves
1000	About 1000 additions and pointer moves

Pattern observation: The work grows directly with the number of elements.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line with the array size.

Common Mistake

[X] Wrong: "Pointer arithmetic makes the code run faster and changes the time complexity."

[OK] Correct: Pointer arithmetic just changes how we access data, but the number of steps still depends on the array size.

Interview Connect

Understanding how loops and pointers work together helps you explain how your code handles data efficiently.

Self-Check

"What if we used two pointers moving from both ends toward the middle? How would the time complexity change?"