Complexity of Treemap insertion vs HashMap insertion

Question

I am confused with the time complexity of these two algorithms.

//time complexity O(nlog(n)) public void usingTreeMap(){     Map<Integer, Integer> map = new TreeMap<Integer, Integer>();     for (int i = 0; i < 10; i++) {         map.put(i, i);     } } //time complexity O(n) public void usingHashMap(){     Map<Integer, Integer> map = new HashMap<Integer, Integer>();     for (int i = 0; i < 10; i++) {         map.put(i, i);     } } 

Is the time complexity to the usingTreeMap algorithm correct.I do know in treemap the insertion time is log(n) but if we iterate over an array of 10 elements does it become nlog(n).

Answer 1

Complexity with HashMap

In the case of HashMap, the backing store is an array. When you try to insert ten elements, you get the hash, compute the specific array index from that hash, and since it's an array in the back, you inject in O(1).

• For first element, time taken to insert = O(1)
• For second element, time taken to insert = O(1)
• .
• .
• For n^th element, time taken to insert = O(1)

So, total time for insertion of n elements in a HashMap = n * O(1) = O(n)

---

Complexity with TreeMap

In this case, the backing store is a Tree. For a tree with total k elements, on an average, the time to find the location is O(Log k).

• Time to insert first element = O(1)
• Time to insert second element = O(Log 1) = 0 = O(1)
• Time to insert third element = O(Log 2)
• .
• .
• Time to insert n^th element = O(Log (n-1))

Total time = Log 1 + Log 2 + Log 3 + ... + Log (n-1)

Now, Log 1 <= Log n, Log 2 <= Log n ... Log (n-1) <= Log n, leading us to n-1 values each of which is less than or equal to Log n.

This means that the timing for insertion in a treemap sum to a value <= (n-1) * Log (n), leading to the complexity of O(n Log (n)).

---

_{One of the properties of logs is Log a + Log b = Log (ab). Using that, the insertion time in case of TreeMap sums to a lesser-known running time value of O(Log(n!)). But, since, O(Log(n!)) is bound by O(n Log(n)), the time complexity of insertion of n elements in a TreeMap is loosely written O(n Log(N)).}