What will be the time complexity of this code? should I assume it as two separate for loops

def f2(list_of_list):
    flat_list = []
    for inner_list in list_of_list:
        flat_list.extend(inner_list)
    return [
        x for i, x in enumerate(flat_list)
        if flat_list.index(x) == i]

CodePudding user response：

The time complexity of your code would be O(n) (n is the length of flat_list). First, find the most time complex top-level loop. That would be the first loop. Then, the first loop appends all the elements of the lists to flat_list, so the loop is run the number of elements in flat_list.

CodePudding user response：

list.extend() has a time complexity of O(k) where k is the length of the list being used as the extension.

list.index() has a time complexity of O(n) in the worst case scenario (value is last element or not in the list)

n = the number of lists in the list_of_lists
m = the total number of elements in all of the lists.

Then the time complexity of the list comprehension will be at best O(m) when every element is identical (making list.index(x) essentially constant time as it always returns 0)

At worst, when every element is unique, it will be O(m²).

The first loop is a linear O(m), as m would be the sum of each k for every call to flat_list.extend()