Address and dereference operators - Time & Space Complexity

Time Complexity: Address and dereference operators

O(n)

Understanding Time Complexity

We want to see how using address and dereference operators affects how long a program takes to run.

Specifically, we ask: does accessing memory with these operators slow down the program as input grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code sums all elements in an integer array using the address and dereference operators.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Accessing each array element by dereferencing a pointer.
• How many times: Exactly once for each element, so n times.

How Execution Grows With Input

As the array size grows, the program does more work by accessing more elements.

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

Pattern observation: The work grows directly with the number of elements; doubling n doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to run grows in a straight line with the size of the input array.

Common Mistake

[X] Wrong: "Using the dereference operator makes the code slower by a lot compared to normal array access."

[OK] Correct: Dereferencing a pointer is essentially how array access works under the hood, so it does not add extra time complexity.

Interview Connect

Understanding how pointer access scales helps you explain memory operations clearly and shows you grasp how programs handle data step-by-step.

Self-Check

"What if we replaced the for-loop with recursion to sum the array? How would the time complexity change?"

Practice

1. What does the & operator do in C?

easy

A. It gives the memory address of a variable.

B. It multiplies two numbers.

C. It dereferences a pointer to get the value.

D. It declares a pointer 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, dereference, or declare pointers; those are different operations.

3. Final Answer:

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

4. Quick Check:

   & means address-of [OK]

Hint: Remember & means 'address of' variable [OK]

Common Mistakes:

• Confusing & with multiplication operator
• Thinking & dereferences a pointer
• Mixing & with pointer declaration

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; is invalid in C (it's C++ reference), int ptr*; and *int ptr; are incorrect syntax.

3. Final Answer:

   int *ptr; -> Option D

4. Quick Check:

   Pointer declaration uses * before variable name [OK]

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

Common Mistakes:

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

3. What is the output of this code?

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

medium

A. 10

B. The memory address of x

C. Garbage value

D. Compilation error

Solution

1. Step 1: Understand pointer assignment

   Pointer p stores the address of x using &x.

2. Step 2: Dereference pointer to get value

   *p accesses the value at the address stored in p, which is 10.

3. Final Answer:

   10 -> Option A

4. Quick Check:

   *p gives value at address [OK]

Hint: *p gives value stored at pointer address [OK]

Common Mistakes:

• Printing pointer variable instead of dereferenced value
• Confusing & and * operators
• Expecting address instead of value

4. Identify the error in this code snippet:

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

medium

A. Incorrect use of & operator.

B. Pointer p is not initialized before dereferencing.

C. Variable x is not declared.

D. Missing semicolon after declaration.

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 assign pointer before dereferencing [OK]

Hint: Initialize pointer before using * to access value [OK]

Common Mistakes:

• Dereferencing uninitialized pointer
• Confusing assignment with address-of
• Ignoring pointer initialization warnings

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

int a = 3, b = 7;
int *p = &a;
*p = *p + 4;
p = &b;
*p = *p - 2;
printf("%d %d", a, b);

hard

A. 7 3

B. 3 5

C. 7 5

D. 7 7

Solution

1. Step 1: Modify value pointed by p initially

   p points to a. *p = *p + 4; changes a from 3 to 7.

2. Step 2: Change pointer to point to b and modify

   p = &b; points to b. *p = *p - 2; changes b from 7 to 5.

3. Step 3: Print final values

   a is 7 and b is 5.

4. Final Answer:

   7 5 -> Option C

5. Quick Check:

   Pointer changes values via dereference [OK]

Hint: Track pointer target and value changes stepwise [OK]

Common Mistakes:

• Not updating the correct variable via pointer
• Confusing pointer assignment with value assignment
• Ignoring pointer reassignment effects