CODEWITHSUNDEEP
algorithmstackcomplexity-theoryspace-complexity
NPS
NPS

Reputation: 6355

Do recursive calls count into space complexity?

When an algorithm doesn't use more than a constant amount of auxiliary memory but does have O(log(N)) recursive calls (each one taking some extra space on the stack), is that algorithm's space complexity O(1) or O(log(N))?

Upvotes: 4

Views: 877

Answers (1)

Timothy Shields
Timothy Shields

Reputation: 79531

If the recursive algorithm is not exploiting tail recursion, then, yes, a straightforward implementation would be using O(log(N)) space. This is because the runtime must keep O(log(N)) stack frames, each of O(1) size, in memory at once.

Upvotes: 7

Related Questions