Recursion: Time and Space Complexity Analysis - 1

The base-case invocation still costs time

A recursive function does work when it reaches its base case too. In countDown, the base case is the condition n == 0. When that condition is true, the function prints nothing and returns, but it still has to enter the invocation, compare n with 0, and perform the return.

void countDown(int n) {
    if (n == 0) {
        return;
    }

    cout << n << " ";
    countDown(n - 1);
}

Starting with countDown(4) creates this sequence of invocations: countDown(4), countDown(3), countDown(2), countDown(1), and countDown(0). The last invocation produces no printed number, but it is still an executed invocation. Leaving it out would leave out its condition check and return.

Five constant-work invocations make countDown(4) part of an O(n) pattern

For countDown(4), there are five invocations and four print operations. Each invocation does only a fixed amount of local work: it checks the condition, may print one value, and may make one recursive call. The number of invocations is therefore the useful count for the running time.

For countDown(n), the arguments are n, n - 1, and so on through 0. That gives n + 1 invocations. Since every invocation performs constant local work, the total running time grows linearly, so countDown(n) has O(n) time complexity. The extra one for the base case does not change the O(n) classification.

A recursive invocation stays active until its deeper call returns

When countDown(4) calls countDown(3), the invocation for 4 does not disappear. It pauses and waits for countDown(3) to return. The same thing happens for 3, 2, and 1. When countDown(0) is reached, the invocations for arguments 4, 3, 2, and 1 are still active and waiting.

At that deepest moment, five countDown stack frames exist at once: one for each argument from 4 through 0. The base-case frame returns first, then the frame for 1, then 2, then 3, and finally 4. Frames disappear one at a time during this return process.

No explicit container does not make the auxiliary space O(1)

The function creates no array, object, or other explicit container, but each active invocation still needs a stack frame. A frame stores the invocation's current state while its deeper recursive call runs. For countDown(4), the peak is five frames. For countDown(n), the peak is n + 1 frames, so the auxiliary space is O(n).

Time and auxiliary space measure different things. Running time counts all the work executed across the entire run, including work in frames that have already returned. Auxiliary space counts memory simultaneously in use, so it is determined by the deepest active stack. Both measurements are O(n) for countDown(n), but they reach that result for different reasons.