I just started learning algorithm using Python. I need some help with analyzing my functions which perform selection sort. I am not so sure about the time and space complexity for my third function, selection_sort3. I am not sure time is of O(n^2) and even less about space is of O(2n). I know the new array being return will double the space. Since I run min on a array with one fewer element in each iteration, does that increase the space used?
def selection_sort1(array): # Time complexity O(n^2), space O(1)
length = len(array)
for i in range(length - 1): # Loop n - 1 times
for j in range(i + 1, length): # Loops n - 1 times
if array[j] < array[i]:
array[i], array[j] = array[j], array[i]
return array
def selection_sort2(array): # Time complexity O(n^2), space O(1)
for i, k in enumerate(array[:-1]): # Loops n - 1 times
for j, v in enumerate(array[1 + i:]): # Loops n - 1 times
if v < k:
array[i], array[j] = array[j], array[i]
return array
def selection_sort3(array): # Time complexity O(n^2), space O(2n) ????
result = []
for i in range(len(array)): # Loops n times
result.append(min(array[i:])) # min function walks through the entire array so its complexity is O(n) ????
return result