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))
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).