Calculating O(n) for a hasmap vs binary search

Question

I'm trying to clarify how to calculate O(n) for the following case:

Given a sorted array, how would you find two numbers whose sum is equal to a given number x in O(n)?

An O(n) solution would be:

1. Remove the first element of the array (e0)
2. Add this to a hashmap
3. Remove the first element of the array (e1)
4. Target is the difference between e1 and x
5. If the target exists in the hash map return the pair
6. Add e1 to the hashmap
7. Repeat steps 3-6 until you find a pair or run out of elements

This would be worst case O(n) as you only need a single pass on the array.

An O(n * log n) solution would be:

1. Remove the first element from the array (e1)
2. Target is the difference between the first element and x
3. Binary search the rest of the array for the target
4. If it exists return the pair
5. Repeat steps 1–4 till you find a pair or run out of elements

This is O(n log n) as you would need to run a binary search (log n) at worst n/2 times giving O(n/2 * log n) which in big O is O(n * log n)

Is this correct?

Answer 1

Yep, for both algorithm ur analysis is correct.

Your first algorithm uses O(n) space also, coz of hashmap. U can avoid that.

Algo : 
1. Consider begin = 0, and end = last_index
2. Consider data[begin] and data[end]
3. If data[begin] + data[end] > req_sum:
        end=end - 1  // u need to decrease ur total sum
   elif data[begin] + data[end] < req_sum:
        begin = begin + 1  // u need to increase ur total sum
   elif data[begin] + data[end] == req_sum:
          print("found")
4. Continue from Step 2.

Obviously avoid case where end < begin and other corner cases .