CODEWITHSUNDEEP
pythonpython-3.xbig-o
theSekyi
theSekyi

Reputation: 530

What is the time complexity of the *in* operation on arrays in python

This code returns the first two numbers in the array that sum up to the targetSum. So for example print(twoNumberSum([3, 5, -4, 8, 11, 1, -1, 6],10)) should return [11,-1]

def twoNumberSum(array,targetSum):
    for i in array:
        remainder = targetSum - i
        if (remainder != i) and (remainder in array):
            return [i,remainder]
    return []

The code works but it is said to execute in O(n) time. My intuition is this - we first loop through the array and choose a number. For each number, we find the remainder. Using each remainder, we again loop through the entire array. Shouldn't this be an O(n^2) operation? Is the in operation in python not an O(n) operation?

Upvotes: 0

Views: 165

Answers (2)

Sumit Jaiswal
Sumit Jaiswal

Reputation: 236

The in operation will have different complexities based on the type of container it is referred to. Here i in array will become array.__contains__(i) and it is referred to a list type container.

  • (list, tuple) as you guessed are O(n).
  • Trees would be average O(log n).
  • set/dict - Average: O(1), Worst: O(n).

See this Document if you have any further queries.

Upvotes: 2

Mooncrater
Mooncrater

Reputation: 4861

Take a look at this. For the case of an list, it makes no sense that this will take less than O(n^2) time. The outer loop takes O(n) time, and for each iteration O(n) time to check if the element is present or not.

If instead of a list, you use a dict, then the in operation is O(1). Then I could say that the whole of this code takes linear time.

Upvotes: 1

Related Questions