def list_copy_rec(list_1, i):
if i == len(list_1):
return []
return [list_1[i]] + list_copy_rec(list_1, i + 1)
I’m not sure what the spatial complexity is.
The algorithm is very simple, its purpose is to copy an entered list to another one. It uses stack recursion, and I think that the spatial complexity is O(n), but I am not quite sure given that the + operator creates an extra list every time (but maybe it’s deleted by the garbage collector), and also the fact that given that it is stack recursion it uses memory to hold the unfinished operations until the end (but then again I’m not sure if that affects the final memory use). I am a beginner on the topic of analyzing algorithm’s complexity, so please be nice 🙂
>Solution :
You’re correct that the algorithm uses recursion, and each recursive call adds a new frame to the stack. Therefore, the stack depth will be (O(n)) for a list of length (n). This accounts for the first component of the spatial complexity.
Regarding the + operator creating a new list: While a new list is created at each recursive call, older lists will be garbage collected after they are no longer in use. However, the sum of all these lists’ sizes will still contribute to the overall spatial complexity.
Combining these two factors, the overall spatial complexity is (O(n) + O(n) = O(n)).
So, yes, you’re correct: the spatial complexity is (O(n)).