1
$\begingroup$

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='')
$\endgroup$
1
  • $\begingroup$ Is anything known about the implementation of check_list/[], of check_list.append()? What about i in check_list? $\endgroup$
    – greybeard
    Sep 21 at 4:52
1
$\begingroup$

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)$

$\endgroup$
3
  • $\begingroup$ Note that $n$ is the size of the input array here. As it stands, the given code just takes constant time. $\endgroup$
    – vonbrand
    Sep 20 at 22:36
  • 1
    $\begingroup$ 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)$. $\endgroup$
    – nir shahar
    Sep 20 at 23:00
  • $\begingroup$ 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... $\endgroup$
    – user206904
    Oct 20 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.