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?"