Java 8: time complexity of map.merge
I am trying to find the complexity below the code, because of the loop for
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 understand the time complexity of the code above and map.merge()
in Java 8.
source to share
As stated in Javadoc JDK 8: https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#merge-KV-java.util.function.BiFunction-
The default implementation is equivalent to doing the following steps on this map, then returning the current value, or null if not present:
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);
Everything put
, remove
and get
are O(1)
for HashMap
. remappingFunction
which you are using, Integer::sum
which has nothing to do with n
. So the for loop in your solution is simple O(n)
.
For a stream operation, stream + map + sum should be roughly equivalent to a simple for loop, making it O(n)
. The lambda you passed to map()
calls map.getOrDefault
, which is also O(1)
for HashMap
. So O(n)
in general.
So your solution is simple O(n)
.
source to share