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 is important to understand how the program's running time changes as the size of the array grows.

We want to know how many steps the program takes when it accesses or processes array elements using pointers.

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++) {
        printf("%d ", *(arr + i));
    }
    printf("\n");
}
    

This code prints each element of an integer array using a pointer to access elements.

Identify Repeating Operations

• Primary operation: Accessing each array element through pointer arithmetic inside the loop.
• How many times: The loop runs exactly size times, once for each element.

How Execution Grows With Input

As the array size grows, the number of steps grows in a straight line with it.

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

Pattern observation: The work grows evenly as the array gets bigger, doubling the size doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the code grows directly in proportion to the number of elements in the array.

Common Mistake

[X] Wrong: "Using pointers makes accessing array elements faster and changes the time complexity."

[OK] Correct: Pointer access and array indexing both take constant time per element, so the overall time still grows linearly with the array size.

Interview Connect

Understanding how pointer and array access scales helps you explain memory handling and performance clearly in interviews.

Self-Check

"What if we used nested loops to process a 2D array with pointers? How would the time complexity change?"

Practice

1. What does a pointer to an array in C typically store?

easy

A. The address of the first element of the array

B. The total number of elements in the array

C. The sum of all elements in the array

D. The value of the last element in the array

Solution

1. Step 1: Understand pointer basics

   A pointer stores a memory address, not values or counts.

2. Step 2: Pointer to array points to first element

   In C, a pointer to an array points to the first element's address.

3. Final Answer:

   The address of the first element of the array -> Option A

4. Quick Check:

   Pointer = first element address [OK]

Hint: Pointers hold addresses, not values or counts [OK]

Common Mistakes:

• Thinking pointer stores array size
• Confusing pointer with array value
• Assuming pointer stores last element

2. Which of the following is the correct way to declare a pointer to an integer array 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 int is declared as int *ptr;

2. Step 2: Check other options for syntax errors

   int ptr[] declares an array, not a pointer; int &ptr is invalid in C; int ptr* is incorrect syntax.

3. Final Answer:

   int *ptr; -> Option B

4. Quick Check:

   Pointer syntax uses * before variable [OK]

Hint: Pointer declaration uses * before variable name [OK]

Common Mistakes:

• Using array syntax instead of pointer
• Confusing C++ reference (&) with pointer
• Placing * after variable name incorrectly

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

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

medium

A. 10

B. 30

C. Garbage value

D. 20

Solution

1. Step 1: Understand pointer arithmetic

   p points to arr[0], so p + 1 points to arr[1].

2. Step 2: Dereference pointer at p + 1

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

3. Final Answer:

   20 -> Option D

4. Quick Check:

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

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

Common Mistakes:

• Confusing *(p+1) with *p
• Assuming pointer arithmetic adds 1 byte
• Expecting arr[0] value instead

4. Identify the error in this C code snippet:

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

medium

A. Missing semicolon after array declaration

B. Array size is incorrect

C. Pointer points outside array bounds causing undefined behavior

D. Pointer declaration syntax is wrong

Solution

1. Step 1: Analyze pointer assignment

   arr + 3 points one element past the last array element (out of bounds).

2. Step 2: Dereferencing out-of-bounds pointer

   *p accesses invalid memory, causing undefined behavior.

3. Final Answer:

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

4. Quick Check:

   Pointer out of array range = error [OK]

Hint: Pointer must stay within array limits [OK]

Common Mistakes:

• Ignoring pointer out-of-bounds access
• Thinking array size is wrong
• Confusing pointer syntax errors

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

int arr[] = {5, 10, 15, 20};
int *p = arr;
for(int i = 0; i < 4; i++) {
    printf("%d ", *(p + i));
}

hard

A. 5 10 15 20

B. 20 15 10 5

C. 5 5 5 5

D. Compilation error

Solution

1. Step 1: Understand the loop and pointer arithmetic

   Loop runs i from 0 to 3, *(p + i) accesses arr[i].

2. Step 2: Print each element in order

   Values printed are arr[0]=5, arr[1]=10, arr[2]=15, arr[3]=20.

3. Final Answer:

   5 10 15 20 -> Option A

4. Quick Check:

   Pointer + i accesses arr[i] in order [OK]

Hint: Pointer + i accesses array element i [OK]

Common Mistakes:

• Assuming reverse order print
• Printing same element repeatedly
• Expecting syntax error