CODEWITHSUNDEEP
pythonlistalgorithmdata-structurestime-complexity
Mohamad Emad
Mohamad Emad

Reputation: 1

What is the big o notation of this code? Is it O(n^2) or O(n)?

Here, the code check if list1 contains some elements of list2?

result = []
    for item in list1:
        if item not in list2:
            result.append(item)

I think that the complexity will be O(n^2) because the (x in s) function is considered as inner loop right?

Upvotes: 0

Views: 130

Answers (3)

Thọ Đỗ Xuân
Thọ Đỗ Xuân

Reputation: 150

in operator's complexity is based on what's the type of your list.
if your lists is python's list type, in here we can see (x in s) with list in python has the complexity of O(n)

so if your list1 has n element, list2 has m element, your code's complexity will be O(n.m)

Upvotes: 0

AlbertFX91
AlbertFX91

Reputation: 108

Your time complexity is O(n). If you are using hashset for the set2 variable, the 'in' operation performs constant in average.

If you use two list, then the time complexity is O(nm) where n = len(list1) and m = len(list2)

Upvotes: 1

Faboor
Faboor

Reputation: 1383

If set2 is an actual set or dict it's O(len(list1)) because x in some_set will be (amortised) O(1).

If list2 is a list, then it's going to be O(len(list1) * max_len(list2)) because x in some_list will need to run through the list in O(len(some_list)). So if both lists can be up to n, then it's going to be O(n^2).

Upvotes: 0

Related Questions