Whats time complexity of this python function?

Question

def hasPairWithSum(arr,target):
     for i in range(len(arr)):
         if ((target-arr[i])  in arr[i+1:]):
             return True

    return False

In python, is time complexity for this function O(n) or O(n^2), in other words 'if ((target-arr[i]) in arr[i+1:])' is this another for loop or no? Also what about following function, is it also O(n^2), if not why:

def hasPairWithSum2(arr,target):
   seen = set() 
   for num in arr:
      num2 = target - num
      if num2 in seen:
         return True
      seen.add(num)
   return False

Thanks!

if ((target-arr[i]) in arr[i+1:]) is another loop. It needs to compare each element of the list arr[i+1:]. A way to avoid this is to create a set, dictionary, or some other data structure that allows constant time inclusion tests. — Mark
– Mark, Commented Dec 13, 2020 at 21:21
Yes, O(n^2) because the x in y is executed as a loop by python. — quamrana
– quamrana, Commented Dec 13, 2020 at 21:22
If you created a s = set(arr) and used in s instead of in arr[i+1:] it would be O(n) — ssp
– ssp, Commented Dec 13, 2020 at 21:23
@MarkMeyer, quamrana Thanks for the reply, I edited the question, can you please reply to that. Thanks! — Neo
– Neo, Commented Dec 13, 2020 at 21:28

trincot · Accepted Answer · 2020-12-14 12:34:09Z

2

The first version has a O(n²) time complexity:

Indeed the arr[i+1:] already creates a new list with n-1-i elements, which is not a constant time operation. The in operator will scan that new list, and in worst case visit each value in that new list.

If we count the number of elements copied into a new list (with arr[i+1), we can sum those counts for each iteration of the outer loop:

  n-1
+ n-2
+ n-3
+ ...
+ 1
+ 0

This is a triangular number, and equals n(n-1)/2, which is O(n²).

Second version

The second version, using a set, runs in O(n) average time complexity.

There is no list slicing here, and the in operator on a set has -- contrary to a list argument -- an average constant time complexity. So now every action within the loop has an (average) constant time complexity, giving the algorithm an average time complexity of O(n).

According to the python docs, the in operator for a set can have an amortised worst time complexity of O(n). So you would still get a worst time complexity for your algorithm of O(n²).

edited Dec 14, 2020 at 12:34

answered Dec 14, 2020 at 12:19

trincot

357k38 gold badges282 silver badges338 bronze badges

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

1 Comment

Neo Over a year ago

Thank you very much trincot!

BadTouchInc · Accepted Answer · 2020-12-13 21:28:41Z

0

It's O(n^2)

First loop will run n times and second will run (n-m) for every n. So the whole thing will run n(n-m) times that is n^2 - nm. Knowing that m<n we know that it has a complexity of O(n^2)

But if it's critical to something you might consult someone who is better at that.

answered Dec 13, 2020 at 21:28

BadTouchInc

32 bronze badges

1 Comment

trincot Over a year ago

m<n is not an enough condition to conclude that n²-nm is O(n²). For instance, if m=n-1, then we have n²-nm = n²-n(n-1) = n. Similarly, if m=n-2, then it will equal 2n... etc.

Collectives™ on Stack Overflow

Whats time complexity of this python function?

2 Answers 2

Second version

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Second version

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related