I have three separate questions on space complexity (please forgive me I am quite novice), though they are all tangentially related:
Suppose we have the function below:
def remove_duplicates(my_list):
return list(set(my_list))
As illustrated above, we are simply converting an inputted list into a set and then re-converting it back to list form. Even though we are not storing this newly created list, does it still contribute towards auxiliary space? That is, is our auxiliary space O(N) or O(1)? Based on my own thinking, I believe it to be O(N), given the fact that we are creating a new list that, at worst, is equivalent in length to our old list. Regardless of if we are assigning it to a variable, we still created it and therefore expended auxiliary space.
Suppose we have the function below:
def foo(my_list):
my_list = list(range(len(my_list)))
As illustrated above, this function is simply creating a new list, which contains all of the indices of the input list. However, we are overwriting our input variable my_list and storing this newly created list there. How do we assess the space complexity of such a decision? Does this make our auxiliary space O(N)? Does this impact our input space complexity, which was originally O(N)?
Suppose we have two functions (no code). Both take in a positive integer n. The first function will return output as a list of lists in the form of [odds, evens], where odds is a list of all the odd numbers up to and including n (starting from 0) and evens is a list of all the even numbers up to and including n (starting from 0). The second function, instead, will return output as a list of integers where each element is an integer between (and including) 0 and n. So, how would we assess the auxiliary space of both functions?
If we just view the size of the two return lists, then the first function's return list will only ever have two elements––an odd list and an even list––whereas the second function's return list will have n + 1 elements, each an integer. From this assessment alone, it is easy to believe that the first function is O(1) auxiliary space while the second is O(N). However, we are neglecting the fact that, in total, the first function's return list will contain roughly n/2 elements in its first list and roughly n/2 elements in its second, which will therefore occupy space linearly. So, which is it? Is the first function O(N) auxiliary space or O(1)?
