Address and dereference operators in C++ - Time & Space Complexity

Time Complexity: Address and dereference operators

O(n)

Understanding Time Complexity

Let's see how using address and dereference operators affects how long a program takes to run.

We want to know how the number of steps changes when we use these operators in code.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code adds up all numbers in an array using pointers and the dereference operator.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through the array and dereferencing each element.
• How many times: Exactly once for each element in the array (size times).

How Execution Grows With Input

Each element requires one dereference and addition, so the total steps grow as the array gets bigger.

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

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 as the array gets bigger.

Common Mistake

[X] Wrong: "Using pointers and dereference operators makes the code run faster or slower in a way that changes the overall time complexity."

[OK] Correct: The operators just access data; the number of times you do this depends on the array size, so the time complexity stays the same.

Interview Connect

Understanding how pointer operations scale helps you explain your code clearly and shows you know what affects performance.

Self-Check

"What if we used a nested loop to sum elements in a 2D array using pointers? How would the time complexity change?"

Practice

1. What does the & operator do in C++?

easy

A. It dereferences a pointer to get the value.

B. It multiplies two numbers.

C. It declares a pointer variable.

D. It gives the memory address of a variable.

Solution

1. Step 1: Understand the & operator

   The & operator is used to get the address of a variable in memory.

2. Step 2: Differentiate from other operators

   It does not multiply, declare pointers, or dereference pointers; those are different operations.

3. Final Answer:

   It gives the memory address of a variable. -> Option D

4. Quick Check:

   & operator = address retrieval [OK]

Hint: Remember & means 'address of' in C++ [OK]

Common Mistakes:

• Confusing & with multiplication operator
• Thinking & declares a pointer
• Mixing & with dereference * operator

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. *int ptr;

Solution

1. Step 1: Recall pointer declaration syntax

   In C++, a pointer to an int is declared as int *ptr; where * indicates pointer type.

2. Step 2: Check other options for syntax errors

   int &ptr; declares a reference, not a pointer. int ptr*; and *int ptr; are invalid syntax.

3. Final Answer:

   int *ptr; -> Option A

4. Quick Check:

   Pointer declaration = int *ptr; [OK]

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

Common Mistakes:

• Using & instead of * for pointers
• Placing * after variable name incorrectly
• Confusing pointers with references

3. What is the output of the following code?

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

medium

A. Address of x

B. 10

C. 20

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.

2. Step 2: Check the effect on x

   Since *p points to x, changing *p to 20 updates x to 20.

3. Final Answer:

   20 -> Option C

4. Quick Check:

   Dereferencing pointer changes original variable [OK]

Hint: Changing *p changes the value of x [OK]

Common Mistakes:

• Thinking *p is the address, not the value
• Expecting output to be original x (10)
• Confusing pointer variable with pointed value

4. Identify the error in this code snippet:

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

medium

A. Variable x is not declared.

B. Pointer p is not initialized before dereferencing.

C. Syntax error in pointer declaration.

D. Cannot assign value to *p.

Solution

1. Step 1: Check pointer initialization

   Pointer p is declared but not assigned an address before *p = x;.

2. Step 2: Understand dereferencing uninitialized pointer

   Dereferencing p without initialization causes undefined behavior or crash.

3. Final Answer:

   Pointer p is not initialized before dereferencing. -> Option B

4. Quick Check:

   Always initialize pointers before dereferencing [OK]

Hint: Initialize pointers before using *p [OK]

Common Mistakes:

• Dereferencing pointer without assigning address
• Assuming pointer auto-points to variable
• Confusing pointer declaration with initialization

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. 4 3

B. 3 4

C. 3 3

D. 4 4

Solution

1. Step 1: Understand pointer swapping

   Initially, p points to a (3), q points to b (4). The code swaps the pointers using temp.

2. Step 2: Check final pointer values

   After swapping, p points to b (4), and q points to a (3).

3. Final Answer:

   4 3 -> Option A

4. Quick Check:

   Pointer swap changes what they point to [OK]

Hint: Swapping pointers swaps the values they point to [OK]

Common Mistakes:

• Confusing swapping pointers with swapping values
• Expecting original order after swap
• Mixing pointer values and pointed values