Time complxity: O(n) or O(n^2) or ...

Question

I wrote a code for the 'find the pair'-challenge.

https://code.sololearn.com/cFYiyaIbMbgo/?ref=app

Part of the challenge is to keep the O as low as possible.
i thought i wrote it O(n) but in the comment some one wrote it is O(n^2).
Can you tell me if it is indeed O(n^2) and why?

https://www.sololearn.com/learn/6362/?ref=app

I even added time measurement per element which seems to indicate O(n) but maybe that is not the right way to check the O?

https://code.sololearn.com/c9X6j4D9c1oC/?ref=app

Answer 1

Python 'in' operator appears to have a worst case of O(n). Wrapping it with a for loop which runs for each element in the list would result in worst case of O(n²). I haven't handtraced the execution yet, but that's probably why your someone was claiming O(n²).

https://stackoverflow.com/questions/13884177/complexity-of-in-operator-in-python

Answer 2

No it's O (n) the for in is not a double loop it's a single one so its O(n)

Answer 3

I get why it is O(n^2) now, thanks @ILYA.
Still don't get why it is not shown by calculated time.

https://www.sololearn.com/learn/6060/?ref=app

Answer 4

Actually it's true that this not the right way to calculate the big-O, because big-O indicates the time for the whole number of operations being executed. Therefore, here since you have calculated the time per list item, it's going to be the same for O(n) and O(n^2), because it's basically the time for only one operation.

Answer 5

Afnan Abed
i would think that in O(n^2) if the number of items x n, the time needed should get x n^2. Thus time per item should increase, no?

Answer 6

davy hermans
no that's not the case. It's that the time for each element stays the same, but the number of elements to be checked while running the code is more in case of O(n^2).
It is that in O(n) it is n elements , but in O(n^2) it is n^2 elements.