Pointer and variable relationship in C++ - Time & Space Complexity

Time Complexity: Pointer and variable relationship

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run code changes when we use pointers and variables together.

Specifically, how does accessing or changing a variable through a pointer affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int main() {
    int x = 10;
    int* p = &x;
    for (int i = 0; i < 1000; i++) {
        (*p)++;
    }
    return 0;
}
    

This code increases the value of x by using a pointer p inside a loop that runs 1000 times.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Incrementing the value pointed to by p (which is x).
• How many times: 1000 times because of the for loop.

How Execution Grows With Input

Each time the loop runs, it does one increment through the pointer.

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

Pattern observation: The work grows directly with the number of loop runs. More loops mean more increments.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line with the number of times the loop runs.

Common Mistake

[X] Wrong: "Using a pointer makes the code slower or more complex in time."

[OK] Correct: Accessing a variable through a pointer is just as fast as direct access in this simple case, so the time depends mainly on the loop count, not the pointer itself.

Interview Connect

Understanding how pointers relate to variables and loops helps you explain how your code runs step-by-step, a skill useful in many programming tasks and interviews.

Self-Check

"What if we changed the loop to run n times instead of 1000? How would the time complexity change?"