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?"

Practice

1. What does a pointer to a pointer store in C?

easy

A. The size of a variable

B. The value of an integer

C. The address of another pointer

D. The address of a function

Solution

1. Step 1: Understand pointer basics

   A pointer stores the address of a variable.

2. Step 2: Understand pointer to pointer

   A pointer to pointer stores the address of another pointer, not a direct value.

3. Final Answer:

   The address of another pointer -> Option C

4. Quick Check:

   Pointer to pointer = address of pointer [OK]

Hint: Pointer to pointer holds address of pointer, not value [OK]

Common Mistakes:

• Confusing pointer to pointer with pointer to value
• Thinking it stores the value directly
• Mixing it with function pointers

2. Which of the following is the correct way to declare a pointer to a pointer to an int in C?

easy

A. int **ptr;

B. int ptr*;

C. int *ptr*;

D. int &ptr*;

Solution

1. Step 1: Recall pointer declaration syntax

   Single pointer to int is declared as int *ptr;.

2. Step 2: Extend to pointer to pointer

   Pointer to pointer uses two asterisks: int **ptr;.

3. Final Answer:

   int **ptr; -> Option A

4. Quick Check:

   Pointer to pointer declaration uses two * [OK]

Hint: Use two * for pointer to pointer declaration [OK]

Common Mistakes:

• Placing * incorrectly in declaration
• Using & instead of *
• Confusing pointer syntax with references

3. What is the output of the following C code?

int x = 10;
int *p = &x;
int **pp = &p;
printf("%d", **pp);

medium

A. Address of x

B. Compilation error

C. Address of p

D. 10

Solution

1. Step 1: Understand variable assignments

   x = 10, p points to x, pp points to p.

2. Step 2: Evaluate **pp

   *pp gives p (pointer to x), **pp gives value at x, which is 10.

3. Final Answer:

   10 -> Option D

4. Quick Check:

   **pp dereferences twice to get x's value [OK]

Hint: Double dereference **pp gets original value [OK]

Common Mistakes:

• Printing pointer address instead of value
• Using single * instead of **
• Confusing *p and **pp

4. Identify the error in the following code snippet:

int x = 5;
int *p = &x;
int **pp;
*pp = p;
printf("%d", **pp);

medium

A. Syntax error in printf

B. pp is not initialized before dereferencing

C. x is not initialized

D. p is not assigned correctly

Solution

1. Step 1: Check pointer initialization

   pp is declared but not initialized to point anywhere.

2. Step 2: Analyze dereferencing *pp = p;

   Dereferencing uninitialized pp causes undefined behavior or crash.

3. Final Answer:

   pp is not initialized before dereferencing -> Option B

4. Quick Check:

   Dereferencing uninitialized pointer causes error [OK]

Hint: Always initialize pointers before dereferencing [OK]

Common Mistakes:

• Assuming pointer auto-initializes
• Ignoring uninitialized pointer usage
• Confusing pointer assignment with value assignment

5. Given the code below, what will be the output?

int a = 3, b = 7;
int *p1 = &a;
int *p2 = &b;
int **pp = &p1;
*pp = p2;
printf("%d %d", *p1, *p2);

hard

A. 7 7

B. 3 7

C. 3 3

D. Compilation error

Solution

1. Step 1: Initial pointer assignments

   p1 points to a (3), p2 points to b (7), pp points to p1.

2. Step 2: Change p1 via pointer to pointer

   *pp = p2 changes p1 to point to b (7).

3. Step 3: Print values

   *p1 now points to b (7), *p2 is 7, so output is "7 7".

4. Final Answer:

   7 7 -> Option A

5. Quick Check:

   Pointer to pointer changed p1 to point to b [OK]

Hint: Pointer to pointer can change pointer target [OK]

Common Mistakes:

• Assuming p1 still points to a
• Confusing *pp and **pp
• Ignoring pointer reassignment effect