1

tuple and list both have constant time O(1) for searching an element, but is it a different constant time for each?

Let's say I have two variables

list1 = ["hello", "how", "are", "you"]
tuple1 = ("hello", "how", "are", "you")

Is there a different constant time for searching in lists:

if "you" in list1:
    print "Found"

vs. tuples:

if "you" in tuple1:
    print "found"
jonrsharpe
  • 115,751
  • 26
  • 228
  • 437
pyman
  • 43
  • 1
  • 3
  • 1
    Do read [Are tuples more efficient than lists in Python?](http://stackoverflow.com/q/68630/4099593). For your particular example, tuple is twice as faster (0.07us vs 0.16us) – Bhargav Rao Sep 25 '15 at 10:10
  • @BhargavRao Why does the python website list it with `O(1)` efficiency? along with lists? maybe a different constant time for each? – pyman Sep 25 '15 at 10:23
  • 2
    Afaik, Using `in` is O(n) efficiency. (Set is O(1)). If you feel that the dupe target does not answer, then please do mention. I will re-open it (But I am sure it will be closed again as it is a very similar question) – Bhargav Rao Sep 25 '15 at 10:29
  • @BhargavRao Edited the question, please check and re-open – pyman Sep 25 '15 at 10:33
  • I edited the title and added a link to this question in the chatroom. Certainly, your question will be answered in a few minutes. – Bhargav Rao Sep 25 '15 at 10:45
  • 3
    But please add a link to where ever you found the time complexity – Bhargav Rao Sep 25 '15 at 10:47
  • Neither is technically O(1) in lookups, although tuples are often considered to be length-bound and thus tuple-lookups could be considered to be "more" O(1) than list lookup – mike3996 Sep 25 '15 at 10:47
  • *"tuple and list both have constant time O(1) for searching an element"* - no, they don't. *"Why does the python website list it with O(1) efficiency?"* - **where** does it do that? *"is it a different constant time for each?"* - big-`O` only allows broad, worst-case comparisons, different implementations may have very different fixed costs for the same scaling factor (and note that e.g. `O(3n)` and `O(2n)` are considered `O(n)`). – jonrsharpe Sep 25 '15 at 10:48
  • I got 88ns vs 90.5ns for tuple1 vs list1 using Python 2.7.10 %timeit and substituting pass for print "found. With Python 3.4.3 they both took 136ns. –  Sep 25 '15 at 10:51
  • Where did you read that list has O(1) for searching an element? In https://wiki.python.org/moin/TimeComplexity it says that the x in s operation is O(n) – YuppieNetworking Sep 25 '15 at 10:52
  • @YuppieNetworking Yes, it is. My mistake. I was quick to assume "Get Item" as search complexity – wolfgang Sep 25 '15 at 11:01
  • Ah, Apologies, Closing this question – wolfgang Sep 25 '15 at 11:01
  • Just to clarify, when we are using "in" operator to check if an element exists, the time complexity for both Lists and Tuple is O(n) but in general tuple is faster due to a lower constant factor? Am I correct? – Inherited Geek May 25 '19 at 17:52

0 Answers0