The recursion bootcamp lists the Euclidean algorithm as an example of GCD. Since, the recursion is implemented as a tail recursion, shouldn’t the space complexity be O(1)?
(EPI Ch15, Pg224) GCD Space Complexity for tail recursion
It is a recursive algorithm so it implicitly uses stack. The algorithm will use O(n) space. What we discussed there is that it can be implemented as an iterative algorithm which will be O(1) space.
0 Likes
Based on https://www.youtube.com/watch?v=L1jjXGfxozc, the language runtime usually optimizes when it sees that a recursion is implemented as a tail recursion i.e. the execution would only need 1 item in the call stack which gets replaced/updated whenever the tail recursion call is made.
0 Likes
Yes, compiler can optimize this during runtime for sure. However, when you are talking about complexity, usually it is language agnostic and platform independent. For example, in C++, some compilers have the option to loop unfolding which flatten loops into fixed number of statements that will remove the time complexity there.
0 Likes
