I was just wondering when understanding the time complexity of an algorithm like the one below.

For a python list, if we have a for loop iterating over it, and then a containment check, would the time complexity of that be O(n^2).

I know both are O(n) (or I think) so having them nested in one another would that make it O(n^2)?

I think if this "list" is actually a list, then the time complexity of the code below is O(n^2). But if it's a dictionary it would be O(n) because lookup is O(1). Is that correct?

Thanks for any help in advance!

```
for element in list:
if x in list:
```

`list`

as a variable name, as you'll shadow the builtin type. Next (andmaybemore relevant), you don't need to test if the list you're iterating over and the one you're checking membership in are the same. The`in`

test will always be true, so there's no need for it. If they're separate lists (or dictionaries) then`O(n^2)`

may not be correct because it assumedbothlists are of size`n`

. If they could have different sizes, you should describe the run time as`O(m*n)`

.