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

Practice

1. What does a pointer variable in C++ store?

easy

A. The value of another variable

B. The memory address of another variable

C. The size of a variable

D. The type of a variable

Solution

1. Step 1: Understand what a pointer is

   A pointer is a variable that stores the address of another variable, not the value itself.

2. Step 2: Differentiate pointer from normal variables

   Normal variables store values directly, but pointers store where those values are located in memory.

3. Final Answer:

   The memory address of another variable -> Option B

4. Quick Check:

   Pointer = address storage [OK]

Hint: Pointers always hold addresses, not values [OK]

Common Mistakes:

• Confusing pointer value with variable value
• Thinking pointer stores variable type
• Assuming pointer stores variable size

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

easy

A. int ptr*;

B. *int ptr;

C. int *ptr;

D. ptr int*;

Solution

1. Step 1: Recall pointer declaration syntax

   In C++, to declare a pointer to an int, you write the type followed by an asterisk and the pointer name.

2. Step 2: Check each option

   Only 'int *ptr;' matches the correct syntax. Others have misplaced asterisks or wrong order.

3. Final Answer:

   int *ptr; -> Option C

4. Quick Check:

   Pointer declaration = type *name [OK]

Hint: Pointer declaration: type *name; [OK]

Common Mistakes:

• Placing * after variable name
• Using * before type keyword
• Mixing order of type and pointer symbol

3. What is the output of the following code?

int x = 10;
int *p = &x;
*p = 20;
std::cout << x << std::endl;

medium

A. 20

B. 10

C. Address of x

D. Compilation error

Solution

1. Step 1: Understand pointer assignment

   Pointer p stores the address of x. Using *p = 20 changes the value at that address, so x becomes 20.

2. Step 2: Output the value of x

   After changing *p, printing x outputs 20.

3. Final Answer:

   20 -> Option A

4. Quick Check:

   Pointer dereference changes variable value [OK]

Hint: Changing *p changes x's value [OK]

Common Mistakes:

• Thinking *p = 20 changes pointer, not value
• Expecting output to be address
• Confusing pointer and variable values

4. Identify the error in the following code:

int x = 5;
int *p;
*p = x;
std::cout << *p << std::endl;

medium

A. Pointer p is not initialized before dereferencing

B. Variable x is not declared

C. Incorrect pointer declaration syntax

D. Missing semicolon after declaration

Solution

1. Step 1: Check pointer initialization

   Pointer p is declared but not assigned an address before using *p = x; which causes undefined behavior.

2. Step 2: Understand dereferencing uninitialized pointer

   Dereferencing p without initialization leads to runtime error or crash.

3. Final Answer:

   Pointer p is not initialized before dereferencing -> Option A

4. Quick Check:

   Always initialize pointers before dereference [OK]

Hint: Initialize pointers before use to avoid errors [OK]

Common Mistakes:

• Dereferencing uninitialized pointers
• Assuming pointer auto-initializes
• Ignoring runtime errors from bad pointers

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

int a = 3, b = 4;
int *p = &a;
int *q = &b;
int *temp = p;
p = q;
q = temp;
std::cout << *p << " " << *q << std::endl;

hard

A. 3 4

B. 3 3

C. 4 4

D. 4 3

Solution

1. Step 1: Understand pointer swapping

   Initially, p points to a (3), q points to b (4). temp stores p (address of a).

2. Step 2: Swap pointers

   p = q makes p point to b (4), q = temp makes q point to a (3).

3. Step 3: Print values pointed by p and q

   *p is 4, *q is 3, so output is "4 3".

4. Final Answer:

   4 3 -> Option D

5. Quick Check:

   Pointer swap changes what they point to [OK]

Hint: Swapping pointers swaps pointed values [OK]

Common Mistakes:

• Confusing pointer values with pointed values
• Mixing up which pointer points where after swap
• Assuming values themselves swap