Forked from iSergius/Java Collections Complexity cheatsheet
Last active
November 12, 2025 17:48
-
-
Save marcinjackowiak/85f144d0f1ed5fd066d4d2a34961497c to your computer and use it in GitHub Desktop.
Revisions
-
marcinjackowiak renamed this gist
Oct 9, 2020 . 1 changed file with 32 additions and 14 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -1,18 +1,20 @@ Big O complexities for common methods of Java Collections and common sorting algorithms. Complexity (Best to Worst) =================================================================================================== O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!) Collections =================================================================================================== List | Add | Remove | Get | Contains | Next | Data Structure ---------------------|------|--------|------|----------|------|--------------- ArrayList | O(1) | O(n) | O(1) | O(n) | O(1) | Array LinkedList | O(1) | O(1) | O(n) | O(n) | O(1) | Linked List CopyOnWriteArrayList | O(n) | O(n) | O(1) | O(n) | O(1) | Array Set | Add | Remove | Contains | Next | Size | Data Structure ----------------------|----------|----------|----------|----------|------|------------------------- HashSet | O(1) | O(1) | O(1) | O(h/n) | O(1) | Hash Table @@ -22,8 +24,6 @@ TreeSet | O(log n) | O(log n) | O(log n) | O(log n) | O(1) | Red-b CopyOnWriteArraySet | O(n) | O(n) | O(n) | O(1) | O(1) | Array ConcurrentSkipListSet | O(log n) | O(log n) | O(log n) | O(1) | O(n) | Skip List Queue | Offer | Peek | Poll | Remove | Size | Data Structure ------------------------|----------|------|----------|--------|------|--------------- PriorityQueue | O(log n) | O(1) | O(log n) | O(n) | O(1) | Priority Heap @@ -36,15 +36,33 @@ SynchronousQueue | O(1) | O(1) | O(1) | O(n) | O(1) | None! DelayQueue | O(log n) | O(1) | O(log n) | O(n) | O(1) | Priority Heap LinkedBlockingQueue | O(1) | O(1) | O(1) | O(n) | O(1) | Linked List Map | Get | ContainsKey | Next | Data Structure ----------------------|----------|-------------|----------|------------------------- HashMap | O(1) | O(1) | O(h/n) | Hash Table LinkedHashMap | O(1) | O(1) | O(1) | Hash Table + Linked List IdentityHashMap | O(1) | O(1) | O(h/n) | Array WeakHashMap | O(1) | O(1) | O(h/n) | Hash Table EnumMap | O(1) | O(1) | O(1) | Array TreeMap | O(log n) | O(log n) | O(log n) | Red-black tree ConcurrentHashMap | O(1) | O(1) | O(h/n) | Hash Tables ConcurrentSkipListMap | O(log n) | O(log n) | O(1) | Skip List Sorting =================================================================================================== Algorithm | Best | Average | Worst | Space Complexity ---------------|--------------|--------------|--------------|------------------ Quicksort | O(n log n) | O(n log n) | O(n^2) | O(log n) Mergesort | O(n log n) | O(n log n) | O(n log n) | O(n) Timsort | O(n) | O(n log n) | O(n log n) | O(n) Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) Bubble Sort | O(n) | O(n^2) | O(n^2) | O(1) Insertion Sort | O(n) | O(n^2) | O(n^2) | O(1) Selection Sort | O(n^2) | O(n^2) | O(n^2) | O(1) Tree Sort | O(n log n) | O(n log n) | O(n^2) | O(n) Shell Sort | O(n log n) | O(n log^2 n) | O(n log^2 n) | O(1) Bucket Sort | O(n+k) | O(n+k) | O(n^2) | O(n) Radix Sort | O(nk) | O(nk) | O(nk) | O(n+k) Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) Cubesort | O(n) | O(n log n) | O(n log n) | O(n) -
Oct 1, 2020 . 1 changed file with 5 additions and 1 deletion.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -1,5 +1,9 @@ Below are the Big O performance of common functions of different Java Collections. Best to Worst: -------------------------------------------------------------------------------------- O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!) List | Add | Remove | Get | Contains | Next | Data Structure ---------------------|------|--------|------|----------|------|--------------- @@ -20,7 +24,7 @@ ConcurrentSkipListSet | O(log n) | O(log n) | O(log n) | O(1) | O(n) | Skip Queue | Offer | Peek | Poll | Remove | Size | Data Structure ------------------------|----------|------|----------|--------|------|--------------- PriorityQueue | O(log n) | O(1) | O(log n) | O(n) | O(1) | Priority Heap LinkedList | O(1) | O(1) | O(1) | O(1) | O(1) | Array -
iSergius created this gist
Sep 3, 2016 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,46 @@ Below are the Big O performance of common functions of different Java Collections. List | Add | Remove | Get | Contains | Next | Data Structure ---------------------|------|--------|------|----------|------|--------------- ArrayList | O(1) | O(n) | O(1) | O(n) | O(1) | Array LinkedList | O(1) | O(1) | O(n) | O(n) | O(1) | Linked List CopyOnWriteArrayList | O(n) | O(n) | O(1) | O(n) | O(1) | Array Set | Add | Remove | Contains | Next | Size | Data Structure ----------------------|----------|----------|----------|----------|------|------------------------- HashSet | O(1) | O(1) | O(1) | O(h/n) | O(1) | Hash Table LinkedHashSet | O(1) | O(1) | O(1) | O(1) | O(1) | Hash Table + Linked List EnumSet | O(1) | O(1) | O(1) | O(1) | O(1) | Bit Vector TreeSet | O(log n) | O(log n) | O(log n) | O(log n) | O(1) | Red-black tree CopyOnWriteArraySet | O(n) | O(n) | O(n) | O(1) | O(1) | Array ConcurrentSkipListSet | O(log n) | O(log n) | O(log n) | O(1) | O(n) | Skip List Queue | Offer | Peak | Poll | Remove | Size | Data Structure ------------------------|----------|------|----------|--------|------|--------------- PriorityQueue | O(log n) | O(1) | O(log n) | O(n) | O(1) | Priority Heap LinkedList | O(1) | O(1) | O(1) | O(1) | O(1) | Array ArrayDequeue | O(1) | O(1) | O(1) | O(n) | O(1) | Linked List ConcurrentLinkedQueue | O(1) | O(1) | O(1) | O(n) | O(n) | Linked List ArrayBlockingQueue | O(1) | O(1) | O(1) | O(n) | O(1) | Array PriorirityBlockingQueue | O(log n) | O(1) | O(log n) | O(n) | O(1) | Priority Heap SynchronousQueue | O(1) | O(1) | O(1) | O(n) | O(1) | None! DelayQueue | O(log n) | O(1) | O(log n) | O(n) | O(1) | Priority Heap LinkedBlockingQueue | O(1) | O(1) | O(1) | O(n) | O(1) | Linked List Map | Get | ContainsKey | Next | Data Structure ----------------------|----------|-------------|----------|------------------------- HashMap | O(1) | O(1) | O(h / n) | Hash Table LinkedHashMap | O(1) | O(1) | O(1) | Hash Table + Linked List IdentityHashMap | O(1) | O(1) | O(h / n) | Array WeakHashMap | O(1) | O(1) | O(h / n) | Hash Table EnumMap | O(1) | O(1) | O(1) | Array TreeMap | O(log n) | O(log n) | O(log n) | Red-black tree ConcurrentHashMap | O(1) | O(1) | O(h / n) | Hash Tables ConcurrentSkipListMap | O(log n) | O(log n) | O(1) | Skip List