CODEWITHSUNDEEP
pythontime-complexitylist-comprehensionnested-listsspace-complexity
Jason Grace
Jason Grace

Reputation: 344

Space Complexity with no variables defined

Suppose I had some code:

def foo(forest: list[list[int]]) -> int:
    return sum([1 for tree in forest for leaf in tree])

In this code, no variables are defined. Everything is evaluated in one line, which means to my knowledge the data isn't being stored anywhere. Does that mean this program has a space complexity of O(1)?

Thanks for your time.

Upvotes: 0

Views: 70

Answers (1)

Jasmijn
Jasmijn

Reputation: 10452

First, what is the n here?

I think there are two different variables of importance here, I'll call them M = len(forest) and K = max(len(tree) for tree in forest).

Then the time complexity would be O(MK).

Next, the list you are constructing has a length of O(MK), so its space complexity is the same as the time complexity.

You can avoid that by using a generator expression instead of a list comprehension, like so:

return sum(1 for tree in forest for leaf in tree if leaf < 0)

This avoids having to store every value, only generating a single value at a time when calculating the sum, so its additional space complexity would be O(1).

Upvotes: 4

Related Questions