2Sum in Constant Time?

Is it possible to solve the two_sum problem in constant time O(1), I asked myself.

Reading through Mr Wengrow's DSA book, I soon come to find out the theoretical reasons why this is impossible.
Three reasons are:

1. Algorithmic time complexity is judged by the worst-case scenario. In 2Sum, the valid pair could be the very last two elements in the array, or there might be no valid pair at all. To confidently declare the result in these cases, I (and the computer :)) are forced to check every single element.

2. A constant-time algorithm performs a fixed number of operations regardless of how large the input grows. An O(1) algorithm would only be able to check a fixed number of array slots (e.g, looking only at the first 5 elements). This works if the array has 5 items, but because algorithmic time complexity is judged by the worst-case scenario, it completely fails if the array has 10 million items and the solution is buried in the middle. The Big O notation story.

3. In computer science, O(1) doesn't literally mean "one single step". It means a constant number of steps that never changes, regardless of how massive the input data gets. If an algorithm required exactly 2 searches, or even 50 searches, to find those two indices, whether the array had ten items or ten billion items, that would still perfectly qualify as O(1) constant time. The reason O(1) is impossible here isn't because I am looking for two items instead of one. It is because finding even a single specific item in an unsorted array without knowing its location beforehand requires scanning the data. Since I don't know where the numbers are, the number of steps I (and the computer, lol) must take scales directly with the size of the array (n), which permanently breaks the rule of constant time.

I must inspect the data at least once, the absolute fastest I can solve 2Sum is linear time, or O(n). This optimal speed is achieved using a Hash Map (One-pass Hash Table):

• I iterate through the array once.
• For each number, I calculate its complement (Target - Current Number).
• I check if the complement already exists in my Hash Map (which takes O(1) time per lookup).
• If it exists, I have my answer. If not, I add the current number to the Hash Map and move to the next, because I iterate exactly once and perform a constant-time lookup at each step, the total time complexity caps perfectly at the theoretical limit of O(n).

In Python it looks like this:

def two_sum(nums, target):
...     container = {} // My HashMap a.k.a Dictionary
...     for index, eachnumber in enumerate(nums):
...         complement = target - eachnumber
...         if complement in container:
...             return [container[complement], index]
...         container[eachnumber] = index
...         
>>> print(two_sum([2, 7, 11, 15], 9))
[0, 1]

Cheers. I trust you learned something.
Cover Image by Ben Fleeson from Pixabay