0

Sorry to be a pain. I know it's a classic and I have checked, but I still can't understand why the time cost is O(n).

Here's my code.

def two_sum(L, sum):
    targets = {}
    for i in range(len(L)):
        if L[i] in targets:
            return (targets[L[i]], i)
        else: targets[sum - L[i]] = i

While I get that L is only iterated over once and that the value look up for a given key is O(1), isn't the search for an actual key in a dict O(n)? Doesn't that mean that for each value in L there is an O(n) look up cost to find if that value is key in the dict, making it a total of O(n^2)?

Apologies if I'm being stupid but when I searched for an answer everyone just seems to be saying the lookup cost in a hash table is O(1), so it's only O(n) * O(1) = O(n).

Edit: Just to clarify, the dict size in this problem grows with n.

Ben Hall
  • 87
  • 1
  • 6
  • 2
    The "value look up for a given key" and the "search for an actual key in a dict" are two ways of saying the same thing, so they can't have different runtimes. It takes O(1) on average to do this. – interjay Apr 27 '22 at 15:57
  • But I thought given a key you could jump to that address in the dict O(1) by peforming some algorithm on that key, but searching if that key is in the dict is more like searching a list? Edit: to be clear, the dict in this example grows with n. – Ben Hall Apr 27 '22 at 16:04
  • @BenHall please check this post for an explanation to your question: [python-dictionary-keys-in-complexity](https://stackoverflow.com/questions/17539367/python-dictionary-keys-in-complexity) – Ryan Wilson Apr 27 '22 at 16:10

1 Answers1

1

Ryan Wilson's link along with interjay's wisdom helped me realise how this works.

It doesn't iterate over a list of keys when you call key in dict, it just hashes the key and sees if it gets a valid answer!

Cheers everyone.

Ben Hall
  • 87
  • 1
  • 6