CODEWITHSUNDEEP
pythonpython-3.xrecursion
idpd15
idpd15

Reputation: 456

What is the space complexity of the following algorithm?

The following algorithm finds the largest element of a list using recursion.

def largest(s):
    if len(s) == 0:
        return 'List can\'t be empty'
    elif len(s) == 1:
        return s[0]
    elif s[0] <= s[1]:
        return largest(s[1:])
    else:
        s.remove(s[1])
        return largest(s)

The time complexity is O(n) because we are making total of n calls to the function largest and each call does O(1) operations.
I am having trouble figuring out the space complexity. I think it's O(n) but I am not sure.

Upvotes: 0

Views: 163

Answers (2)

Vlad Costin
Vlad Costin

Reputation: 1105

First of all, the time complexity is not O(n) because the list.remove operation is not O(1), but O(n). So your time complexity would be O(n^2) - Imagine applying largest over this array [5 4 3 2 1] You can see here a list of python operation complexity.

The space complexity is O(n^2) because when you are doing return largest(s[1:]) you are copying the list, not getting a reference, so you're keeping all the intermediate cuts of the list. Doing s.remove(s[0]) and then return largest(s) will give you O(n) space complexity because you're working with references.

Upvotes: 1

Christoph Burschka
Christoph Burschka

Reputation: 4689

Slicing a standard list does create a (shallow!) copy of the slice. You're correct about this making it O(n). (In additional memory allocated; not counting the list itself, which is of course already in memory.)

As Reut points out in the comments, this is an implementation detail of the Python interpreter, but I couldn't say for sure whether any interpreters handle slices differently. Any implementation that does create a slice without copying would have to use copy-on-write instead.

Upvotes: 0

Related Questions