Analyzing Space Complexity of Recursive Function

Question

In our CS course, we haven't covered how to analyse space complexity. We have though, been given the task of implementing an $\Theta(n)-time$ algorithm for reversing a singly linked list, with a maximum $O(1)-space$ (besides the actual array).

This is my implementation in Python:

#x0.next = x1
def invert(x0,x1):
    next = x1.next
    x1.next = x0
    if next is None:
        return x1
    else:
        invert(x1,next)

def invertSLinkyList(head):
    firstNext = head.next
    head.next = None
    x = 0
    x = invert(head,firstNext)
    return x

To give a quick verbal description: Essentially, we iterate through each node (x0) and set its next (x1) to the previous node. We then call this recursively on the original next (x1) on its next (x1.next), until we reach the end node (which has next = None) at which case we return this node as the new head.

I have analysed its time complexity to be $\Theta(n)$ based on:

Each call creates 1 child note at a constant time
We create n children as the code iterates through the whole list.
It takes $O(1)$ to "merge"

My question is then; How do I go about analysing its space complexity?

OBS: Please not that this is not a graded assignment. It is a part of my weekly training exercises.

Jav Solo · Accepted Answer · 2022-03-15 21:53:59Z

1

To analyze space complexity, you are analyzing whether the amount of memory is dependent on n. In other words, as your algorithm input size changes, number of nodes for the LL in this case, does that affect the space used?

In this case, by using recursion, you are adding frames to the call stack and using memory that way. Since you mention that you make a recursive call per node, can you reason the space complexity? How does that relate to your entries?

In this case, you won't return until next is none, at that point how many stack frames would be added to the call stack?

In this case, n frames would be put on the call stack, therefore you would get a Space complexity of O(n)

edited Mar 15, 2022 at 21:53

answered Mar 14, 2022 at 15:46

Jav Solo

8161 gold badge9 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

GeorgeWTrump Over a year ago

If I understand your questions correctly; We're "saving" the x0 and x1 for each call, until we reach xn where xn.next = Null. Since this is basically iterating over the array of size n, the O(f) = O(n)? More specifically, if an integer's memory space is k, T(n) = 2*k*n? Also, I just assumed it; But does Python save the variables until the last return?

Jav Solo Over a year ago

I am not sure what you mean by O(f), but you can think of it as adding one frame to the call stack until you reach n and at that point, you begin popping frames off the stack as they each return. I am also not sure what you mean by T(n) (Theta perhaps), but this question is independent of the language memory implementation. However, k is constant, 2 is constant, and you are left with O(n) as the space complexity. Constants can be dismissed (dropped if you will) in time and space complexity analysis.

GeorgeWTrump Over a year ago

T(n) = The actual specific running time. O(f) big O of my function - but I didn't define f so of course, that is a mistake on my behalf. But you did answer my question (both of them,) so thank you very much! :) (Also you should edit your answer, so I can accept it as an actual answer ;) )

user20329607 · Accepted Answer · 2022-10-25 11:05:53Z

0

Find the time and space complexity of following code.

def list_sum_recursive(input_list): # Base case if input_list == []: return 0

# Recursive case
else:
    head = input_list[0]
    smaller_list = input_list[1:]
    return head + list_sum_recursive(smaller_list)

#Driver Code print(list_sum_recursive([1, 2, 3]))

answered Oct 25, 2022 at 11:05

user20329607

1

Collectives™ on Stack Overflow

Analyzing Space Complexity of Recursive Function

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related