CODEWITHSUNDEEP
pythonbig-o
user9352220
user9352220

Reputation: 95

Working out the time complexity

I have have the following code:

for i in alist:
    if i not in alist:
        result.append(i)

I am not sure whether that would be O(n) or O(n^2), because of the in statement?

Upvotes: 0

Views: 41

Answers (1)

Volodymyr Synytskyi
Volodymyr Synytskyi

Reputation: 4055

That would be O(n^2) because you have two loops(one of them is nested inside another one) which iterate through all elements in the list. One loop caused by "in" another one caused by "not in".

You can read more about implementation details of "in" and "not in" here.

Also "in" and "not in" operators may have different implementation for different data types as well as different algorithm complexity.

Upvotes: 1

Related Questions