-1
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?

Pash0002
  • 110
  • 2
  • 14
Rattla
  • 1

1 Answers1

0

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.

Mukit09
  • 2,956
  • 3
  • 24
  • 44