Time complexity in Python 3

Question

The following code works in a hackerrank problem: (A and B will get non repetitive and discrete data by default)

n,m = map(int,input().split())
arr = list(map(int,input().split()))
A = set(map(int,input().split()))
B = set(map(int,input().split()))
count = 0
for x in arr:
    if x in A:
        count+=1
    if x in B:
        count-=1
print(count)

But the next one shows time error in 4 test cases:

n,m = map(int,input().split())
arr = list(map(int,input().split()))
A = list(map(int,input().split()))
B = list(map(int,input().split()))
count = 0
for x in arr:
    if x in A:
        count+=1
    if x in B:
        count-=1
print(count)

How the time complexity changed sharply in list and set and how do they work?

Well, yes, in set is much more efficient than in list. For significantly large inputs, that can be significant. — deceze
– deceze ♦, Commented Oct 19, 2019 at 14:56
A search for python time complexity returns many SO results - maybe there is one that will suffice. Otherwise: wiki.python.org/moin/TimeComplexity — wwii
– wwii, Commented Oct 19, 2019 at 14:56

6502 · Accepted Answer · 2019-10-19 14:57:49Z

2

set in Python is implemented using an hash table.

Checking if an element is present or not in a set is a O(1) (i.e. constant time) operation and execution time for this check does not depend on how many elements are in the set.

list is instead implemented as an array and checking if an element is present requires O(n) where n is the number of elements in the list. Checking if an element is present in a list containing 1000 elements is going to take ten times the time that would be needed if the list contained 100 elements only.

answered Oct 19, 2019 at 14:57

6502

115k17 gold badges177 silver badges277 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

6502 Over a year ago

@VISHALAGRAWAL: yes, you can use tuples with sets, provided it's a tuple of objects you can put in sets (for example it's forbidden to put lists because those are mutable objects, and you cannot put a tuple if one of the elements of the tuple is a list)

Acorn · Accepted Answer · 2019-10-19 15:49:32Z

0

The lines that change are:

A = list(map(int,input().split()))
B = list(map(int,input().split()))

For the good case, you use set rather than list. This has an impact when you do:

if x in A:
if x in B:

because that checks whether an element is in the list/set.

For lists, this is O(n) because you will have to perform a linear search since it is an unordered container.
For sets, in Python they are implemented with a hash table, which means that you will likely have an average O(1) time lookup, but note that the docs aren't explicit about what kind of hashing is used. Therefore, you have to assume a worst case of O(n).

edited Oct 19, 2019 at 15:49

answered Oct 19, 2019 at 14:57

Acorn

26.4k7 gold badges50 silver badges78 bronze badges

1 Comment

VISHAL AGRAWAL Over a year ago

for sets it is O(1) not O(log n) still thanks for help

Collectives™ on Stack Overflow

Time complexity in Python 3

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related