Buiding a hash table or a dictionary - complexity

Question

Just came across this question:

Sub-set sum problem : Finding the count of two pairs of numbers in a given array whose sum is equal to a given number

Eg: Given sum is 9 and array is { 0, 1, 2, 7, 13 } => O/P is 1 pair (2 and 7)

Seems like this can be achieved in O(n) (Build a hash-table or a dictionary, iterate every element of the given array and subtract from the given sum, check if the resultant number is in array)

Obviously, iterating through every element of array takes O(n) time.

My question is what is the time complexity and the space complexity for building the hash-table or the dictionary ?

Note 1: My guess is O(n) for building the hash-table or the dictionary, again we have to iterate through each and every element in the array. Is this correct ?

Note 2: So, the complexity is O(n) + O(n) = 2 * O(n) right? (But the answer seems to be just O(n))

Answer 1

Seems right that time complexity will be O(n), not O(n) + O(n) = 2 * O(n).

To insert element in hash table is constant operation so it will take O(1) time and you are doing here that operation n time, so it will be O(n) * O(1).

So eventually it will be O(n).

Data Structure with Time & Space Complexity.

Answer 2

Your guess is right.

Timecomplexity and space complexity for hashtable is same O(n).

As explained by you, since you need to store all elements in hashtable which takes O(n) timecomplexity and O(N) space complexity.