Array Reversal Techniques in DSA C - Time & Space Complexity

Time Complexity: Array Reversal Techniques

O(n)

Understanding Time Complexity

We want to understand how the time needed to reverse an array changes as the array gets bigger.

How does the number of steps grow when the array size grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void reverseArray(int arr[], int n) {
    int start = 0, end = n - 1;
    while (start < end) {
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}
    

This code reverses the elements of an array by swapping pairs from the start and end moving towards the center.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Swapping two elements inside a while loop.
• How many times: The loop runs about n/2 times, where n is the array size.

How Execution Grows With Input

As the array size grows, the number of swaps grows roughly half as fast.

Input Size (n)	Approx. Operations
10	5 swaps
100	50 swaps
1000	500 swaps

Pattern observation: The number of operations grows linearly with the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to reverse the array grows directly in proportion to the array size.

Common Mistake

[X] Wrong: "Reversing an array takes constant time because we just swap elements."

[OK] Correct: Even though each swap is quick, the number of swaps grows with the array size, so total time grows too.

Interview Connect

Knowing how array reversal scales helps you understand basic array operations and prepares you for more complex problems.

Self-Check

"What if we used recursion to reverse the array instead of a loop? How would the time complexity change?"