Recursion on Arrays and Strings in DSA C - Time & Space Complexity

Time Complexity: Recursion on Arrays and Strings

O(n)

Understanding Time Complexity

When using recursion on arrays or strings, we want to know how the time needed grows as the input gets bigger.

We ask: How many steps does the recursion take as the array or string length increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int sumArray(int arr[], int n) {
    if (n == 0) {
        return 0;
    }
    return arr[n - 1] + sumArray(arr, n - 1);
}
    

This function adds all elements of an array by calling itself with a smaller size each time.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive call reducing array size by one each time.
• How many times: Exactly n times, where n is the array length.

How Execution Grows With Input

Each recursive call does one addition and calls itself with one less element.

Input Size (n)	Approx. Operations
10	10 additions and 10 calls
100	100 additions and 100 calls
1000	1000 additions and 1000 calls

Pattern observation: Operations grow directly with input size; doubling input doubles work.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete grows in a straight line with the size of the array or string.

Common Mistake

[X] Wrong: "Recursion is always slower and more complex than loops."

[OK] Correct: Recursion here simply replaces a loop doing the same work; both have similar time complexity.

Interview Connect

Understanding recursion time helps you explain your solutions clearly and choose the best approach confidently.

Self-Check

"What if we changed the recursion to process two elements per call instead of one? How would the time complexity change?"