0

Let's say you do the following:

for row in myListofLists:
  if tuple(row) in myDictWithTupleKeys:

in other words, within a loop through the rows of an n x n array, you check to see if a row is contained as a key within a dict. Is this an O(n^2) operation? In other words, is the in operator an O(n) operation here?

user129393192
  • 797
  • 1
  • 8
  • 1
    Does this answer your question? [How does python compute the hash of a tuple](https://stackoverflow.com/questions/49722196/how-does-python-compute-the-hash-of-a-tuple) or [How does hash() compute the hash of a tuple?](https://stackoverflow.com/questions/51593173/how-does-hash-compute-the-hash-of-a-tuple) – jtbandes Aug 12 '23 at 23:16
  • So a tuple's hash depends on the hash of its elements, and that can also be some large number deep @jtbandes, but presumably, in a simple tuple of integers, that makes it O(n) the tuple size, assuming the hash of ints is an O(1) operation? – user129393192 Aug 12 '23 at 23:19
  • 2
    That is correct. – user2357112 Aug 12 '23 at 23:19
  • 1
    `tuple(row)` is already O(n) anyway. – juanpa.arrivillaga Aug 13 '23 at 02:25

0 Answers0