This is a companion discussion topic for the original entry at https://www.raywenderlich.com/977854-data-structures-algorithms-in-swift/lessons/2
This is a companion discussion topic for the original entry at https://www.raywenderlich.com/977854-data-structures-algorithms-in-swift/lessons/2
Hello Guys,
Great video.
Isn’t the running time of a dictionary lookup slightly more than O(1)? Wouldn’t it only be O(1) if there was never any collisions?
Thanks,
Chris
Hi Chris!
Unfortunately Big O notation is just a rough categorization! Dictionary lookup would be an amortized O(1), because we expect that hash collisions will be rare. In the absolute worst-case scenario, where every element has the same hash value, you’d have O(n). But again, that’s the worst-case and not the performance you’d normally expect.
Another way of putting it is that O(1) means that the execution time does not increase as n increases, so dictionaries of 10, 100, or 1000 elements will usually perform about the same.
1 Like