Pointers to pointers in C - Time & Space Complexity

Time Complexity: Pointers to pointers

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run code with pointers to pointers changes as the input size grows.

Specifically, we ask: how many steps does the program take when it uses pointers to pointers?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void updateValues(int **ptr, int n) {
    for (int i = 0; i < n; i++) {
        *(*ptr + i) = i * 2;
    }
}
    

This code updates an array of integers using a pointer to a pointer, setting each element to twice its index.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that updates each element in the array.
• How many times: It runs exactly n times, once for each element.

How Execution Grows With Input

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

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

Pattern observation: The work grows directly with n; doubling n 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 size of the input array.

Common Mistake

[X] Wrong: "Using pointers to pointers makes the code slower and more complex, so it must increase time complexity."

[OK] Correct: The pointer type does not change how many times the loop runs; it only changes how we access memory. The time depends on the loop, not the pointer level.

Interview Connect

Understanding how pointers to pointers affect time helps you explain memory access clearly and shows you can analyze code beyond just syntax.

Self-Check

"What if we added a nested loop inside the existing loop that also runs n times? How would the time complexity change?"