Calculate space complexity of list comprehension-CodePudding

I have written the below code:

nums = [0,2,1,5,3,4]

Here, nums is an array of distinct integers from 0 to nums.length - 1

def new_array(nums):
  return [nums[num] for num in nums]

Please help me understand if the space complexity of above code is O(n) or O(1).

My understanding is that the space complexity is O(n) because a new list is created via list comprehension.

How the above code can be rewritten with space complexity O(1)?

CodePudding user response：

You're creating a new list, so the space complexity is `O(n)`.

A list comprehension returns a new list, and the list you construct contains the same number of elements as the original list. The memory used to store the elements of the list you pass in and the memory used to store the elements of the returned list are separate.

CodePudding user response：

According to python documentation (https://docs.python.org/3/tutorial/datastructures.html?highlight=comprehension) list comprehension is a syntax sugar for a standard for so your code is equivalent to the following

nums = [0,2,1,5,3,4]

def new_array(nums):
  L = []
  for num in nums:
    L.append(nums[num])
  return L

Which is O(n)

You're creating a new list, so the space complexity is O(n).

You're creating a new list, so the space complexity is `O(n)`.