could someone help to get the space complexity for this python function?

input: nums = [1, 2, 3, 4, 5, 6, 7, 8....]
       m = integer 

for i in range(len(nums)):
    temp = nums[i:i m]

should this space complexity as o(m), or o(n*m), and why? Thank you!

CodePudding user response：

Not including the input, with that piece of code since m doesn't seem to be a constant, it should just be O(m) because at any given point in time, we are only storing 1 chunk of nums[i:i m] because temp is just reassigned with a new sublist for every loop thus making the previous sublist to be subject for garbage collection already.

• So regardless if there are 1 million nums and m is only 5, then we would only be storing 5 items now, then next iteration leave that previous 5 items and store a new set of 5 items (depending on python implementation, this might even just use the same memory used and overwrite the previous one), and so on.

But if you are storing each sublist such as:

temp_list = []
for i in range(len(nums)):
    temp = nums[i:i m]
    temp_list.append(temp)

Then it should be O(m * len(nums)) because we will be storing m items for each element in nums.

CodePudding user response：

Ignoring Python's garbage collection, you get space complexity of O(mn), where n = len(nums). That's because you first allocate a list of n elements, and then you allocate n lists of m elements each (note that slicing a list creates a new allocation). That gives a total of n mn cell allocations, which is asymptotically O(mn).

But the lists created in the for loop are all referenced by temp. That means that as soon as a new list is created, the previous one has no references and it becomes eligible for garbage collection. That leaves us practically with two lists: nums with length of n, and the last temp with length of m, which amounts to space complexity of O(m n).