Time complexity in Python 3

user_9042071 0
Viewed 288

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?

time-complexity python-3.x python
2 Answers

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.

user_3207260

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

user_93053980
Related