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