What is Performance of Various Java Collection Implementations/Algorithms? What is Big ‘O’ notation for each of them?

by

Each java collection implementation class have different performance for different methods, which makes them suitable for different programming needs.

The performance of various Java collection implementations and algorithms can vary based on the specific use case and the operations being performed. The Big O notation is a way to express the time complexity of algorithms in terms of their input size.

Here is a general overview of the Big O notation for some common Java collection implementations:

  1. ArrayList:
    • Access (get): O(1)
    • Insert (add at end): O(1) amortized, O(n) in worst case
    • Insert (add at arbitrary position): O(n)
    • Remove: O(n)
  2. LinkedList:
    • Access (get): O(n)
    • Insert (add at end): O(1)
    • Insert (add at arbitrary position): O(1)
    • Remove: O(1)
  3. HashMap:
    • Search (get): O(1) average case, O(n) worst case
    • Insert: O(1) average case, O(n) worst case
    • Remove: O(1) average case, O(n) worst case
  4. TreeMap:
    • Search (get): O(log n)
    • Insert: O(log n)
    • Remove: O(log n)
  5. HashSet:
    • Add: O(1) average case, O(n) worst case
    • Remove: O(1) average case, O(n) worst case
    • Contains: O(1) average case, O(n) worst case
  6. TreeSet:
    • Add: O(log n)
    • Remove: O(log n)
    • Contains: O(log n)

It’s important to note that these are general characteristics, and the actual performance can depend on factors such as the specific operations being performed, the size of the collection, and the underlying implementation details.

When discussing performance, it’s also essential to consider factors like space complexity, constant factors, and hidden overhead, which are not always captured by Big O notation but can impact the practical performance of an implementation.