Pointers and arrays in C++ - Time & Space Complexity

Time Complexity: Pointers and arrays

O(n)

Understanding Time Complexity

When working with pointers and arrays, it's important to know how the time to access or process elements changes as the array size grows.

We want to understand how the number of steps grows when we use pointers to traverse arrays.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void printArray(int* arr, int size) {
    for (int i = 0; i < size; i++) {
        std::cout << *(arr + i) << " ";
    }
    std::cout << std::endl;
}
    

This code prints all elements of an integer array using a pointer.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Accessing each element via pointer arithmetic and printing it.
• How many times: Exactly once for each element, so size times.

How Execution Grows With Input

As the array size grows, the number of steps to print all elements grows directly with it.

Input Size (n)	Approx. Operations
10	10 element accesses and prints
100	100 element accesses and prints
1000	1000 element accesses and prints

Pattern observation: Doubling the array size doubles the work done.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the task grows in direct proportion to the number of elements.

Common Mistake

[X] Wrong: "Using pointers makes accessing elements faster, so time complexity is constant."

[OK] Correct: While pointers can be efficient, accessing each element still requires a step, so the total time grows with the number of elements.

Interview Connect

Understanding how pointer traversal scales helps you explain array processing clearly and confidently in interviews.

Self-Check

"What if we used a nested loop to compare each element with every other element? How would the time complexity change?"

Practice

1. What does the name of an array represent in C++?

easy

A. A copy of the entire array

B. The total size of the array

C. The last element of the array

D. A pointer to the first element of the array

Solution

1. Step 1: Understand array name behavior

   In C++, the name of an array acts as a pointer to its first element, not the whole array or size.

2. Step 2: Confirm pointer usage

   This pointer can be used to access elements by pointer arithmetic or indexing.

3. Final Answer:

   A pointer to the first element of the array -> Option D

4. Quick Check:

   Array name = pointer to first element [OK]

Hint: Remember array name points to element zero [OK]

Common Mistakes:

• Thinking array name stores size
• Confusing array name with last element
• Assuming array name copies data

2. Which of the following is the correct way to declare a pointer to an integer array named arr?

easy

A. int *ptr = &arr;

B. int ptr = &arr;

C. int *ptr = arr;

D. int ptr = arr;

Solution

1. Step 1: Understand pointer declaration

   To declare a pointer to an integer, use int *ptr. The array name arr acts as a pointer to its first element.

2. Step 2: Assign pointer correctly

   Assigning ptr = arr; sets the pointer to the first element's address. Using &arr gives the address of the whole array, which has a different type.

3. Final Answer:

   int *ptr = arr; -> Option C

4. Quick Check:

   Pointer to first element = int *ptr = arr [OK]

Hint: Use int *ptr = arr; to point to array start [OK]

Common Mistakes:

• Using &arr instead of arr for pointer
• Declaring pointer as int instead of int*
• Assigning pointer without *

3. What is the output of the following code?

int arr[] = {10, 20, 30};
int *p = arr;
std::cout << *(p + 1) << std::endl;

medium

A. 20

B. 10

C. 30

D. Compilation error

Solution

1. Step 1: Understand pointer arithmetic

   Pointer p points to arr[0]. Adding 1 moves pointer to arr[1].

2. Step 2: Dereference pointer at new position

   Dereferencing *(p + 1) gives the value at arr[1], which is 20.

3. Final Answer:

   20 -> Option A

4. Quick Check:

   *(p + 1) = arr[1] = 20 [OK]

Hint: Pointer + 1 points to next array element [OK]

Common Mistakes:

• Confusing pointer arithmetic with addition of values
• Dereferencing pointer without offset
• Expecting compilation error

4. Identify the error in the following code snippet:

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

medium

A. Pointer declaration is correct, no error

B. Incorrect pointer assignment: &arr should be arr

C. Dereferencing pointer is invalid syntax

D. Array size is too small for pointer arithmetic

Solution

1. Step 1: Analyze pointer assignment

   arr is an array name acting as pointer to first element. &arr is address of whole array, type int (*)[3], incompatible with int *.

2. Step 2: Correct pointer assignment

   Assigning int *p = arr; is correct to point to first element. Using &arr causes type mismatch and incorrect pointer arithmetic.

3. Final Answer:

   Incorrect pointer assignment: &arr should be arr -> Option B

4. Quick Check:

   Use arr, not &arr, for int* pointer [OK]

Hint: Use arr, not &arr, when assigning int* pointer [OK]

Common Mistakes:

• Using &arr instead of arr for int*
• Ignoring pointer type mismatch warnings
• Assuming &arr points to first element

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

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

hard

A. 20

B. 15

C. Undefined behavior

D. 10

Solution

1. Step 1: Understand pointer initialization

   p = arr + 1; points to arr[1], which is 10.

2. Step 2: Access element using pointer indexing

   p[2] means *(p + 2), which points to arr[3] (1 + 2 = 3), value 20.

3. Final Answer:

   20 -> Option A

4. Quick Check:

   p[2] = arr[3] = 20 [OK]

Hint: Pointer[index] = *(pointer + index) [OK]

Common Mistakes:

• Confusing p[2] with arr[2]
• Forgetting pointer offset starts at arr + 1
• Assuming p[2] is out of bounds