Consider an algorithm for reversing a sequence given below:

def reverse(S, start, stop):
    if start < stop − 1:
       S[start], S[stop−1] = S[stop−1], S[start]
       reverse(S, start+1, stop−1)

The time complexity of this algorithm is $O(n)$ because we make $n$ recursive calls each taking at most $O(1)$ time.

But what about the space complexity, It seems that the space complexity of a recursive function is equal to the number of recursive calls. I see that we make $n$ recursive calls but can the space complexity be $O(n)$ when we are not returning to the calling function (no return)? In other words, why not just delete the activation frame when we jump to the next one since we do not need it anymore because we have no more work to do there.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.