Pointer arithmetic in C++ - Time & Space Complexity

Time Complexity: Pointer arithmetic

O(n)

Understanding Time Complexity

Let's see how the time needed changes when we use pointer arithmetic in C++.

We want to know how the number of steps grows as we move through memory with pointers.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code adds up all numbers in an array using a pointer that moves through the array.

Identify Repeating Operations

Look for loops or repeated steps.

• Primary operation: The for-loop that moves the pointer and adds values.
• How many times: Exactly once for each element in the array (size times).

How Execution Grows With Input

As the array gets bigger, the loop runs more times, adding each number.

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

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 with the array size.

Common Mistake

[X] Wrong: "Pointer arithmetic makes the code run faster and changes the time complexity."

[OK] Correct: Pointer arithmetic just changes how we access data, but the number of steps still depends on the array size.

Interview Connect

Understanding how loops and pointers work together helps you explain how your code handles data efficiently.

Self-Check

"What if we used two pointers moving from both ends toward the middle? How would the time complexity change?"

Practice

1. What does adding 1 to a pointer in C++ do when the pointer points to an int array?

easy

A. Moves the pointer to the next integer element in the array

B. Increases the pointer's memory address by 1 byte

C. Moves the pointer to the next byte in memory

D. Causes a compilation error

Solution

1. Step 1: Understand pointer arithmetic basics

   Adding 1 to a pointer moves it to the next element of the type it points to, not just 1 byte.

2. Step 2: Apply to int pointer

   Since int usually occupies 4 bytes, adding 1 moves the pointer by 4 bytes to the next integer.

3. Final Answer:

   Moves the pointer to the next integer element in the array -> Option A

4. Quick Check:

   Pointer + 1 = next element [OK]

Hint: Pointer + 1 moves to next element, not next byte [OK]

Common Mistakes:

• Thinking pointer arithmetic adds 1 byte always
• Confusing pointer increment with byte increment
• Assuming pointer arithmetic causes errors

2. Which of the following pointer arithmetic expressions is syntactically correct in C++?

easy

A. 1 + ptr

B. All of the above

C. ptr - 1

D. ptr + 1

Solution

1. Step 1: Check pointer addition syntax

   Adding an integer to a pointer like ptr + 1 is valid and moves the pointer forward.

2. Step 2: Check commutativity and subtraction

   Integer + pointer like 1 + ptr is also valid due to commutativity. Pointer - integer like ptr - 1 moves pointer backward and is valid.

3. Final Answer:

   All of the above -> Option B

4. Quick Check:

   Pointer + int and int + pointer both valid [OK]

Hint: Pointer + int and int + pointer both work [OK]

Common Mistakes:

• Assuming int + pointer is invalid
• Thinking pointer - int is not allowed
• Confusing pointer arithmetic with pointer subtraction

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

int arr[] = {10, 20, 30, 40};
int *p = arr;
int *q = arr + 3;
std::cout << q - p << std::endl;

medium

A. 3

B. 4

C. 30

D. Compilation error

Solution

1. Step 1: Understand pointer subtraction

   Subtracting two pointers gives the number of elements between them, not bytes.

2. Step 2: Calculate difference between pointers

   q = arr + 3 points to the 4th element, p = arr points to the 1st. Difference is 3 elements.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Pointer difference = number of elements [OK]

Hint: Pointer subtraction returns element count, not bytes [OK]

Common Mistakes:

• Thinking pointer subtraction returns byte difference
• Confusing pointer difference with array values
• Expecting compilation error

4. Identify the error in the following code snippet:

int arr[5] = {1, 2, 3, 4, 5};
int *p = arr + 5;
std::cout << *p << std::endl;

medium

A. Array size is incorrect

B. Syntax error in pointer initialization

C. Pointer points outside array bounds, causing undefined behavior

D. Dereferencing pointer is valid and prints 5

Solution

1. Step 1: Analyze pointer initialization

   p = arr + 5 points one past the last element (index 5), which is outside the array bounds.

2. Step 2: Check dereferencing pointer

   Dereferencing *p here is undefined behavior because pointer is out of valid range.

3. Final Answer:

   Pointer points outside array bounds, causing undefined behavior -> Option C

4. Quick Check:

   Dereferencing out-of-bounds pointer is unsafe [OK]

Hint: Pointer must not dereference beyond array end [OK]

Common Mistakes:

• Assuming pointer at arr+5 is valid to dereference
• Confusing pointer arithmetic with array indexing
• Ignoring undefined behavior risks

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

int arr[] = {5, 10, 15, 20, 25};
int *p = arr + 1;
int *q = arr + 4;
int diff = q - p;
std::cout << *(p + diff) << std::endl;

hard

A. Undefined behavior

B. 20

C. Compilation error

D. 25

Solution

1. Step 1: Calculate pointer difference

   q - p = (arr + 4) - (arr + 1) = 3 elements difference.

2. Step 2: Evaluate pointer arithmetic and dereference

   p + diff = (arr + 1) + 3 = arr + 4, which points to the element 25. Dereferencing gives 25.

3. Final Answer:

   25 -> Option D

4. Quick Check:

   Pointer arithmetic + dereference = correct element [OK]

Hint: Pointer difference + pointer = new pointer position [OK]

Common Mistakes:

• Confusing pointer difference with value difference
• Miscalculating pointer arithmetic
• Assuming undefined behavior without reason