2

From my understanding a hashmap insertion is O(1) and for an arraylist the insertion is O(n) since for the hashmap the hashfunction computes the hashcode and index and inserts the entry and an array list does a comparison every time it enters a new element.

Arvind Talmask
  • 79
  • 1
  • 5
  • I assume, when you are inserting an element into array list using the method list.add(obj), its pretty straight forward. It do in O(1) as it know what is the current size and it would like to insert at the end. O(n) holds good when you try to insert using list.add(index, object) where it need swap n-index elements accordingly. Its just my assumption. – HJK May 06 '15 at 03:17

2 Answers2

6

Firstly, an operation of complexity O(1) does not always take lesser time than an operation of complexity O(n). O(1) only means that the operation takes a constant time (which could be any value), regardless of the size of the input. O(n) means that the time required for the operation increases linearly with the size of the input. This means that O(1) is theoretically guaranteed to take lesser time than O(n) only when n is infinity.

Now coming to your examples, ArrayList.add() operation runs in amortized constant time, which means although it could take up to O(n) time for a particular iteration, the average complexity spread out over time is O(1). For more information on amortized constant time, refer to this question.

Community
  • 1
  • 1
kaykay
  • 556
  • 2
  • 7
  • The meaning of amortized O(1) time is that O(1), not O(n), is the average complexity spread out over time. Individual operations can take O(n), but k add operations will take O(k) total time. – Louis Wasserman May 06 '15 at 16:30
0

ArrayList is faster than the HashMap when you add item at the last of the ArrayList because there is no need to shift the elements in the ArrayList to the right side, you can see the efficiency of the HashMap if you add an item at the front of the ArrayList like this arrayList.add(0, str).

when check this use 1000 as outer loop instead of 100000 otherwise it may hang.

friendlyBug
  • 518
  • 5
  • 12