There is an algorithm that finds a unique element in the list:

#!/usr/bin/env python3 def find_uniq_1(arr): a, b = set(arr) # O(len(arr)) return a if arr.count(a) == 1 else b # O(n) print(find_uniq_1([ 1, 1, 1, 2, 1, 1 ]))

It consists of only two lines of code. I determined the complexity of each line, but I find it difficult to choose the one that more influences the final complexity of the algorithm. Help me please.

I tried to increase the number of arguments and measure the execution time. As a result, I see that the graph grows almost linearly. That is, O (n) is most likely what I need. But I don’t understand why O (n) should have preferred O (len (arr)).

Are there any rules on this?

  • 3
    think what is here n - MBo 6:51 pm
  • one
    By the way, why does set () return a tuple? - MBo 6:58 pm
  • @MBo as far as I can see, there is no tuple in my code. I simply assign the elements of a set to ordinary variables ... Or did I not correctly understand the question? - cyklop77
  • @MBo, apparently, this is somehow related to the fact that there are only one and two in the input list. If there is a guarantee that there will always be a sequence of two unique elements in the list, then this will work. But it looks really very unreliable. - Xander
  • one
    @ cyklop77, MBo implied that multiple assignment implies an implicit coercion to a tuple with its subsequent unpacking. The pitfall here is that your entry implies that there will always be exactly two variables. However, set does not give any guarantees for the number of elements at all - it can return more and less. If you are sure that there will always be only two values ​​- then, in principle, your version is normal, it just looks strange from the side. - Xander

1 answer 1

Linear complexity is when the number of computational iterations is linearly dependent on the NUMBER of ELEMENTS IN THE INPUT DATA.

The length of the input array is the number of elements at the input.

That is, your O(len(arr)) is just a non-standard recording method for O(n) .