CODEWITHSUNDEEP
algorithmhashmapcomplexity-theorybinary-searchcomputation-theory
amay0048
amay0048

Reputation: 1091

Calculating O(n) for a hasmap vs binary search

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?

Upvotes: 0

Views: 77

Answers (2)

pseudo_teetotaler
pseudo_teetotaler

Reputation: 1575

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 .

Upvotes: 2

einpoklum
einpoklum

Reputation: 132128

This sounds like a homework assignment problem in some course you're taking. I won't solve it for you - although it is easy enough to find the solution online - but I will tell you that I am 99% certain that your solution must take O(n) time as the worst-case complexity. Hash-based solutions only take O(1) time per lookup on the average.

Upvotes: 1

Related Questions