Quiz on hashing q3

#1

Using Hashing finding a pair in the array (of length n) having a given sum has time complexity of:

How is this O(n). shouldn’t be it O(1)?

#2

hello @nilotpal

we cant solve it in O(1).
we know only sum and we need to find a and b such that a+b=sum

clearly we nneed to iterate for all element (a) and then for other elemnt (sum-a) we can check using hashmap which makes it o(n)

1 Like