Two sum running time O(n^2) or O(n)

Question

For the two sum problems, find two numbers in a list that adds up to the target.

My solution is to create a dictionary/hash_table, and then store everything in it as (value, index) [Note: For duplicate numbers in the list: higher index would override lower index]

Then traverse through the list again to find the other item.

def twoSum(nums, target): 
    lookup = dict((v, i) for i, v in enumerate(nums))
    for i, v in enumerate(nums):
        if target - v in lookup and i != lookup[target-v]:
            return [lookup[target - v], i]

I think the above algorithm would take O(n * n/2) =, hence O(n^2) time but I see some others say that it only takes linear time. Can someone confirm on this?

Answer 1

That algorithm takes constant time because the operation target - v in lookup runs in constant time. There is only one depth of for loop.

def twoSum(nums, target):
    lookup = dict((v, i) for i, v in enumerate(nums)) # N
    for i, v in enumerate(nums):  # N
        if target - v in lookup and i != lookup[target - v]: # average constant
            return [lookup[target - v], i]  # constant

If you perform an O(N) operation followed by another O(N) operation, the sequence is still O(N).

Here we're talking only about average time complexity. It's possible to have a really bad hashing function with a lot of collisions, such that target - v in lookup actually takes O(N) time, so the worst-case complexity is actually O(N^2). But with a dict you're unlikely to run into this scenario.