Compare complexities of traversing a list v/s using set in python code

Question

I want to ask the difference in time complexities of the following 2 approaches:

1. Without using set as in CODE 1
2. Using set as in CODE 2

Function remove_duplicates() takes in an UNSORTED list and removes elements of the list that are the same.

CODE 1

def remove_duplicates(input_list):
    result = []
    k = -1      # to store the index of current element being checked
    for i in input_list:
        k += 1
        flag = False
        for j in range(0,k,+1):
            if(input_list[j] == i):
                flag = True
        if(flag==False):
            result.append(i)
        else:
            continue
    return result

CODE 2

def remove_duplicates(input_list):
    return list(set(input_list))

Answer 1

Since you are asking for complexity, let’s take a look at your first solution:

The outer loop will run n times, with n being the length of the list. For each iteration, you are then iterating again over the first k elements. So if we just count all the inner loops, we have like n + (n-1) + (n-2) + … + 2 + 1 iterations. This is O(n²) though.

To check the set solution, we have to understand how this works. Creating a set from a list will iterate the list exactly once. For each element we find in the list, that element will be added to the set. Adding to a set is done in (average) constant time. So in total, this is O(n).

Another solution would be to sort the list first, and then iterate once over it to find duplicates. So we would have X + O(n) where X is the complexity of the sort algorithm. Since we can’t sort faster than O(n), that complexity will determine the complexity of the full algorithm.

As for space complexity, the first and the third can be done in-place so we at most need constant space. The set needs O(n) on worst case.