Pointer arithmetic - Time & Space Complexity

Time Complexity: Pointer arithmetic

O(n)

Understanding Time Complexity

We want to see how the time to run code with pointer arithmetic changes as the input size grows.

How does moving pointers through an array affect the number of steps the program takes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void printArray(int *arr, int n) {
    int *ptr = arr;
    for (int i = 0; i < n; i++) {
        printf("%d\n", *ptr);
        ptr++;
    }
}
    

This code prints each element of an integer array using pointer arithmetic to move through the array.

Identify Repeating Operations

• Primary operation: Loop that moves the pointer and prints each element.
• How many times: Exactly once for each element in the array, so n times.

How Execution Grows With Input

Each element causes one print and one pointer move, so the steps grow directly with the number of elements.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: The work grows evenly as the input size grows; doubling the input 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 number of elements.

Common Mistake

[X] Wrong: "Pointer arithmetic makes the code run faster, so time complexity is less than O(n)."

[OK] Correct: Pointer arithmetic is just a way to access elements; it does not reduce the number of steps needed to process each element.

Interview Connect

Understanding how pointer arithmetic affects time helps you explain how low-level code works efficiently, a useful skill in many programming tasks.

Self-Check

"What if we replaced the for loop with a while loop that stops when the pointer reaches the end? How would the time complexity change?"

Practice

1. What does adding 1 to a pointer in C do?
int *p;

easy

A. Causes a syntax error

B. Moves the pointer by 1 byte

C. Moves the pointer to the previous element

D. Moves the pointer to the next element of the type it points to

Solution

1. Step 1: Understand pointer arithmetic basics

   In C, 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 the given pointer

   Since p is an int*, p + 1 points to the next int in memory.

3. Final Answer:

   Moves the pointer to the next element of the type it points to -> Option D

4. Quick Check:

   Pointer + 1 moves by element size [OK]

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

Common Mistakes:

• Thinking pointer arithmetic moves by 1 byte
• Confusing pointer increment with value increment
• Assuming pointer addition causes errors

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

int arr[5];
int *p = arr;

easy

A. p + 2

B. p ++ 2

C. p + ++ 2

D. p +* 2

Solution

1. Step 1: Review pointer arithmetic syntax

   Valid pointer arithmetic uses p + n or p - n where n is an integer.

2. Step 2: Check each option

   p + 2 is valid syntax. Options A, C, and D contain invalid operators or spacing causing syntax errors.

3. Final Answer:

   p + 2 -> Option A

4. Quick Check:

   Correct pointer addition syntax is p + n [OK]

Hint: Pointer arithmetic uses '+' or '-' with integers only [OK]

Common Mistakes:

• Using invalid operators like '++' incorrectly
• Adding spaces that change meaning
• Confusing pointer increment with addition

3. What is the output of this code?

int arr[] = {10, 20, 30, 40};
int *p = arr;
printf("%d", *(p + 2));

medium

A. 10

B. 20

C. 30

D. 40

Solution

1. Step 1: Understand pointer and array relation

   Pointer p points to arr[0], which is 10.

2. Step 2: Calculate pointer offset

   *(p + 2) accesses the element 2 positions after arr[0], which is arr[2] = 30.

3. Final Answer:

   30 -> Option C

4. Quick Check:

   Pointer + 2 points to third element = 30 [OK]

Hint: *(p + n) accesses nth element after pointer [OK]

Common Mistakes:

• Confusing index starting at 1 instead of 0
• Dereferencing pointer without offset
• Mixing pointer arithmetic with array indexing

4. Identify the error in this code snippet:

int arr[3] = {1, 2, 3};
int *p = arr + 3;
printf("%d", *p);

medium

A. Syntax error in pointer declaration

B. Pointer points beyond array bounds causing undefined behavior

C. Missing semicolon after array initialization

D. Incorrect printf format specifier

Solution

1. Step 1: Analyze pointer assignment

   p = arr + 3 points to one element past the last valid element (index 3 in a 3-element array).

2. Step 2: Understand dereferencing invalid pointer

   Dereferencing *p here causes undefined behavior because it accesses memory outside the array.

3. Final Answer:

   Pointer points beyond array bounds causing undefined behavior -> Option B

4. Quick Check:

   Pointer must not dereference beyond array end [OK]

Hint: Pointer + array size points just past array, not valid to dereference [OK]

Common Mistakes:

• Assuming pointer can safely dereference past array end
• Confusing pointer arithmetic with array length
• Ignoring undefined behavior risks

5. Given two pointers int *p1 and int *p2 pointing inside the same array, what does p2 - p1 represent?

hard

A. The number of elements between the two pointers

B. The difference in memory addresses as a raw number

C. The number of bytes between the two pointers

D. A syntax error because pointers cannot be subtracted

Solution

1. Step 1: Understand pointer subtraction in C

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

2. Step 2: Apply to pointers inside the same array

   Since p1 and p2 point inside the same array, p2 - p1 counts how many elements separate them.

3. Final Answer:

   The number of elements between the two pointers -> Option A

4. Quick Check:

   Pointer subtraction = element count difference [OK]

Hint: Pointer subtraction counts elements, not bytes [OK]

Common Mistakes:

• Thinking subtraction returns byte difference
• Assuming pointer subtraction is invalid
• Confusing pointer subtraction with pointer addition