Time complexity for HashMap put/get inside for?

Suppose I have the following code fragment:

for(int i=0; i < n.length(); i++) {
    int aux = n[i];
    if(map.containsKey(aux)) {
        map.put(aux, map.get(aux)+1);
    } else {
        map.put(aux, 1);
    }
}

My map is a HashMap. I know the for would be O(n) then map operations have O(1), however I have three map operations there (containsKey, put and get) so would that be O(3n) or still O(n)?? And why?

Answer

O(3N) and O(N) would be just considered O(N).


I guess, maybe getOrDefault() would be an option, if I’d correctly recall:

for (int i = 0; i < n.length(); i++) {
    int aux = n[i];

    map.put(aux, map.getOrDefault(aux, 0) + 1);
}

and your time and memory complexity would be both O(N).


I think another more readable version would be:

for (int i = 0; i < n.length(); i++) {
    int aux = n[i];

    map.put(aux, -~map.getOrDefault(aux, 0));
}

-~x is just a bitwise operation for x + 1 (-~x = x + 1). However, you can use whichever you would be comfortable.


Thanks to ciamej in the comment!

Leave a Reply

Your email address will not be published. Required fields are marked *