for loop {
    initialize new hashmap 
    for loop {
        if (hashmap.containsKey(i)
             map.put(something)
    }
}

basically 2 nested for loops with a containsKey function inside it.

im thinking its O(n^2) because of the nested loops but it could also be O(n^3) because of the containsKey function. could someone help me out here?

CodePudding user response：

It actually depends on which implementation of the map is being used on your code.Suppose, for HashMap implementaion, it is O(1), but for TreeMap implementaion it O(log(N)). For details, you can see these:

Big-O summary for Java Collections Framework implementations?

https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#containsKey-java.lang.Object-

So, if you use HashMap, then time complexity is O(N^2), and if you use TreeMap, it will be O(N^2)(log(N)) in your case.

CodePudding user response：

Yes you're right it's actually O(n^2). The .put() and .containsKey() of hashmap takes only O(1) in general. But keep in mind for the bad hashcode implementation these constant operations can be O(logN) but it's a rare case. So the overall dominating factor is O(n^2).

Learn more about the time complexity of java hashmap operations

Hope it helps!