CODEWITHSUNDEEP
algorithmrecursionbig-operformance
Popcorn
Popcorn

Reputation: 5348

Is best Big O Time efficiency always the same as best Space efficiency for recursive solutions?

If a recursive solution ends up calling itself consecutively for say, ~N times, before going back up a level, the space efficiency is O(N) at best, because each of the N calls uses up a certain amount of stack space.

Does this also imply the time efficiency is also O(N) at best, because the code inside the recursive function is similar to an inner loop code that gets run ~N times?

Upvotes: 0

Views: 182

Answers (3)

jpalecek
jpalecek

Reputation: 47770

No, but your observation has some truth in it - basically if you know that any algorithm (recursive or otherwise, since we don't distinguish the two; and there isn't anything really that could distinguish them, it's more a matter of style) for a given problem has space complexity at least f(n), it must have time complexity at least f(n), too.

Upvotes: 1

Dai
Dai

Reputation: 155698

In addition to @Ben's answer there is also the case of "tail recursion" where the current stack frame is removed and replaced by the callee's stack frame, but only when the caller's last action is to return the result of a callee. This can result in O(n) time functions having O(1) space when implemented in an entirely functional language.

Upvotes: 2

Ben
Ben

Reputation: 2510

No, since each step of the recursive algorithm can take longer than O(1). If each step take O(n) then the total time complexity is O(n^2).

Upvotes: 0

Related Questions