CODEWITHSUNDEEP
arrayspython-3.xalgorithmdata-structurestime-complexity
Hrishabh Divya
Hrishabh Divya

Reputation: 11

What is the Time Complexity Of the following code ? I am Confused

array = [1,2,4,5]
sum = 3
def arrfilter2(arr):
    for i in arr:
        if ((sum-i) in arr):
            return True
    return False
print(arrfilter2(array))

enter image description here

Upvotes: 1

Views: 339

Answers (2)

Akshit Methi
Akshit Methi

Reputation: 21

The time complexity is O(n^2) in the worst case. In Python, if you search an element using in then it scans through the array linearly to find the element. To compute the Complexity of an algo, in a naive sense, it is O(n^< no of nested loops>). Here you have two nested so it is O(n^2).

you can make it efficient by sorting it first and then using binary search instead of searching linearly using in

Upvotes: 0

OmG
OmG

Reputation: 18838

If the array is not sorted, (sum - i) in arr takes O(n) (n is the length of the array). In the worst case, the loop scans all of the array. Therefore, the time complexity is O(n^2).

By the way, in the best case, it can be resolved in O(1).

If the array is sorted, you can do it better by the binary search technique instead of "in" operator. In that case, the worst case will be O(n log n).

Upvotes: 3

Related Questions