What's the time and space complexity my function

Viewed 41

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
0 Answers
Related