# What is the Big-O Time Complexity of this code?

I was wondering if someone could please explain what the time complexity is for the code below.

I think it would be $$O(n)$$ because the algorithm will take as much time to execute as there are elements in $$n$$.

sample_list = [0, 1, 2, 3, 4, 5, 5, 6]
check_list = []
for i in sample_list:
if i not in check_list:
check_list.append(i)
else:
print(i,end='')

• Is anything known about the implementation of check_list/[], of check_list.append()? What about i in check_list? Sep 21 at 4:52

The code takes $$O(n^2)$$. It is tricky to see that, since its very easy to miss the fact that if i not in sample_list takes another $$O(n)$$ time - just by itself.

Here is the breakdown of the complexity:

check_list = [] # O(1)
for i in sample_list # repeats n times
if i not in check_list: # takes an O(n) time to do the check
check_list.append(i) # takes constant time
else:
print(i) # again, constant time


Overall, it will take $$O(n)$$ per call to if i not in check_list, which will happen exactly $$n$$ times - and hence the total complexity is $$n\cdot O(n)=O(n^2)$$

• Note that $n$ is the size of the input array here. As it stands, the given code just takes constant time. Sep 20 at 22:36
• I assumed sample_list is a general input, and sample_list=[0,1,2,3,4,5,6] is just an example. You are right that technically the code as it is right now takes $O(1)$. Sep 20 at 23:00
• I would have answered like @nirshahar, I would assume the array is not constant, it is just an example to run the code. The question seems to me about the algorithm, not the a specific instance. Any ready to run code can be seen as $O(1)$ if we consider every single array we see in an example a constant... Oct 20 at 21:54