What is the Big-O complexity of my code?

Question

Given an array of integers, write a method which returns all unique pairs which add up to 100.

Example data:

sample_data = [0, 1, 100, 99, 0, 10, 90, 30, 55, 33, 55, 75, 50, 51, 49, 50, 51, 49, 51]
sample_output = [[1,99], [0,100], [10,90], [51,49], [50,50]]

I was solving this problem this weekend and while my solution seems scalable and efficient, I wanted to determine what the worst case time complexity of my solution is?

Here's my solution:

def solution(arr)
  res = []
  h = Hash.new

  # this seems to be O(N)
  arr.each do |elem|
    h[elem] = true
  end

  # how do I determine what Time complexity of this could be?
  arr.each do |elem|
    if h[100-elem]
      h[100-elem] = false
      h[elem] = false
      res << [elem, 100-elem]
    end
  end
  res 
end

If both the loops are O(N) each, and I add them up: O(N + N), this would equal O(2N) and taking the 2 to be a constant, can I assume my solution is O(N) ?

Answer 1

You are correct. Big-O of this code will be O(n) if you consider amortized runtime of hash search/insert.

If you take the true-worst case of hash search/insert (O(n)), then it will be O(n^2).

See Wikipedia on Hash Tables

Answer 2

The question may be asking about the time complexity of hash, but for the particular problem, that hash would better implemented as an array of bools indexed by the input 0..sum (100 in this case). That will have best, worst and average case constant time.

That approach has a simpler to compute complexity of O(N).