Java 8 : map.merge time complexity

Question

I am trying to find the complexity of below code, because of for loop it will be O(n * complexity_of_map.merge)

public int solution(int K, int[] A) {    
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for(int i =0; i < A.length; i++){
        map.merge(K - A[i], 1, Integer::sum);
    }   
    return Arrays.stream(A).map(element -> map.getOrDefault(element,0)).sum();
} 

Can someone help me to understand the time complexity of above code and map.merge() in Java 8.

Answer 1

As quoted from Javadoc of JDK 8: https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#merge-K-V-java.util.function.BiFunction-

The default implementation is equivalent to performing the following steps for this map, then returning the current value or null if absent:

V oldValue = map.get(key);
V newValue = (oldValue == null) ? value :
          remappingFunction.apply(oldValue, value);
if (newValue == null)
    map.remove(key);
else
    map.put(key, newValue);

All put, remove and get are O(1) for HashMap. remappingFunction you are using is Integer::sum which has nothing to do with n. So the for loop in your solution is simply O(n).

For the stream operation, stream + map + sum should be roughly equivalent to a simple for loop, which makes it O(n). The lambda you passed to map() is calling map.getOrDefault, which is also O(1) for HashMap. So that's also O(n) overall.

So your solution is simply O(n).