CODEWITHSUNDEEP
pythonbig-o
Ryan
Ryan

Reputation: 11

What would be the computational complexity in Big-O notation for this function?

I'm trying to solve the LeetCode problem "TwoSum" with an algorithm that is less than O(n^2) time complexity. Previously I solved this with two loops but I wanted to make it more efficient. This is what I have as of right now.

def twoSum(self, nums, target):
    for i in range(len(nums)):
        diff=target-nums[i]
        lower=nums[:i]
        upper=nums[i+1:]
        if (diff in lower or diff in upper):
            ind=[i, nums.index(diff)]
    return ind

I was trying to solve this without a nested for loop but I know the runtime of the "in" operator is O(n) when used with lists. Therefore is the method I wrote still in O(n^2) time?

Upvotes: 0

Views: 65

Answers (1)

M. Chak
M. Chak

Reputation: 532

It's still O(n^2) since you still have two nested loops. First, you have that outer for loop that loops through each item in numbers. Then, you do another loop through the list (although it's masked) to check if the number is in lower or upper. The failure to check nums[i] in the second loop doesn't matter since O(n^2-n) is still O(n^2).

Upvotes: 2

Related Questions