Array sorting algorithms
| Algorithm |
Best |
Average |
Worst |
| Quick Sort | Ω(n log n) | Θ(n log n) | O(n²) |
| Merge Sort | Ω(n log n) | Θ(n log n) | O(n log n) |
| Timsort | Ω(n) | Θ(n log n) | O(n log n) |
| Heap Sort | Ω(n log n) | Θ(n log n) | O(n log n) |
| Bubble Sort | Ω(n) | Θ(n²) | O(n²) |
| Insertion Sort | Ω(n) | Θ(n²) | O(n²) |
| Selection Sort | Ω(n²) | Θ(n²) | O(n²) |
| Tree Sort | Ω(n log n) | Θ(n log n) | O(n²) |
| Shell Sort | Ω(n log n) | Θ(n(log n)²) | O(n(log n)²) |
| Bucket Sort | Ω(n+k) | Θ(n+k) | O(n²) |
| Radix Sort | Ω(nk) | Θ(nk) | O(nk) |
| Counting Sort | Ω(n+k) | Θ(n+k) | O(n+k) |
| Cubesort | Ω(n) | Θ(n log n) | O(n log n) |
| Smooth Sort | Ω(n) | Θ(n log n) | O(n log n) |
| Tournament Sort | — | Θ(n log n) | O(n log n) |
| Stooge Sort | — | — | O(nlog 3/log 1.5) |
| Gnome / Stupid Sort | Ω(n) | Θ(n²) | O(n²) |
| Comb Sort | Ω(n log n) | Θ(n²/p²) | O(n²) |
| Odd Even Sort | Ω(n) | — | O(n²) |
Data structures
S = Sorted, US = Unsorted. Binary heap heapify: O(n).
Same average and worst case
| Structure |
Access |
Search |
Insertion |
Deletion |
| Array | Θ(1) | Θ(n) | Θ(n) | Θ(n) |
| Stack | Θ(n) | Θ(n) | Θ(1) | Θ(1) |
| Queue | Θ(n) | Θ(n) | Θ(1) | Θ(1) |
| Singly Linked List | Θ(n) | Θ(n) | Θ(1) | Θ(1) |
| Doubly Linked List | Θ(n) | Θ(n) | Θ(1) | Θ(1) |
| B Tree | Θ(log n) | Θ(log n) | Θ(log n) | Θ(log n) |
| Red Black Tree | Θ(log n) | Θ(log n) | Θ(log n) | Θ(log n) |
| Splay Tree | — | Θ(log n) | Θ(log n) | Θ(log n) |
| AVL Tree | Θ(log n) | Θ(log n) | Θ(log n) | Θ(log n) |
Different average vs worst case
| Structure |
Average |
Worst |
|
Access | Search | Insert | Delete |
Access | Search | Insert | Delete |
| Skip List | Θ(log n) | Θ(log n) | Θ(log n) | Θ(log n) | O(n) | O(n) | O(n) | O(n) |
| Binary Search Tree | Θ(log n) | Θ(log n) | Θ(log n) | Θ(log n) | O(n) | O(n) | O(n) | O(n) |
| KD Tree | Θ(log n) | Θ(log n) | Θ(log n) | Θ(log n) | O(n) | O(n) | O(n) | O(n) |
| Hash Table | — | Θ(1) | Θ(1) | Θ(1) | — | O(n) | O(n) | O(n) |
Heap operations
| Structure |
Find Max |
Extract Max |
Increase Key |
Insert |
Delete |
Merge |
| Linked List (S) | O(1) | O(1) | O(n) | O(n) | O(1) | O(m+n) |
| Linked List (US) | O(n) | O(n) | O(1) | O(1) | O(1) | O(1) |
| Binary Heap | O(1) | O(log n) | O(log n) | O(log n) | O(log n) | O(m+n) |
| Pairing Heap | O(1) | O(log n) | O(log n) | O(1) | O(log n) | O(1) |
| Binomial Heap | O(1) | O(log n) | O(log n) | O(1) | O(log n) | O(log n) |
| Fibonacci Heap | O(1) | O(log n) | O(1) | O(1) | O(log n) | O(1) |
Graph data structure
| Representation |
Storage |
Add Vertex |
Add Edge |
Remove Vertex |
Remove Edge |
Query |
| Adjacency list | O(|V| + |E|) | O(1) | O(1) | O(|V| + |E|) | O(|E|) | O(|V|) |
| Incidence list | O(|V| + |E|) | O(1) | O(1) | O(|E|) | O(|E|) | O(|E|) |
| Adjacency matrix | O(|V|²) | O(|V|²) | O(1) | O(|V|²) | O(1) | O(1) |
| Incidence matrix | O(|V| · |E|) | O(|V| · |E|) | O(|V| · |E|) | O(|V| · |E|) | O(|V| · |E|) | O(|E|) |
Searching algorithms
| Algorithm | Time |
|---|
| Linear Search | O(n) |
| Binary Search | O(log n) |
| Jump Search | O(√n) |
| Interpolation Search | O(log log n) best, O(n) worst |
| Exponential Search | O(log n) |
| Sequential Search | O(n) |
| Depth first search (DFS) | O(|V| + |E|) |
| Breadth first search (BFS) | O(|V| + |E|) |
Graph algorithms
| Algorithm | Average | Worst |
|---|
| Dijkstra | O(|E| log |V|) | O(|V|²) |
| A* search | O(|E|) | O(bd) |
| Prim | O(|E| log |V|) | O(|V|²) |
| Bellman Ford | O(|E| · |V|) | O(|E| · |V|) |
| Floyd Warshall | O(|V|³) | O(|V|³) |
| Topological sort | O(|V| + |E|) | O(|V| + |E|) |
Time complexity for Java collections
List
| Collection |
Add |
Remove |
Get |
Contains |
Data structure |
| ArrayList | O(1) | O(n) | O(1) | O(n) | Array |
| LinkedList | O(1) | O(1) | O(n) | O(n) | Linked List |
| CopyOnWriteArrayList | O(n) | O(n) | O(1) | O(n) | Array |
List: Add is O(1) amortized for ArrayList. LinkedList Remove is O(1) at head/tail, O(n) by index.
Set
| Collection |
Add |
Contains |
Next |
Data structure |
| HashSet | O(1) | O(1) | O(h/n) | Hash Table |
| LinkedHashSet | O(1) | O(1) | O(1) | Hash Table + Linked List |
| EnumSet | O(1) | O(1) | O(1) | Bit Vector |
| TreeSet | O(log n) | O(log n) | O(log n) | Red black tree |
| CopyOnWriteArraySet | O(n) | O(n) | O(1) | Array |
| ConcurrentSkipListSet | O(log n) | O(log n) | O(1) | Skip List |
Queue
| Collection |
Offer |
Peek |
Poll |
Size |
Data structure |
| PriorityQueue | O(log n) | O(1) | O(log n) | O(1) | Priority Heap |
| LinkedList | O(1) | O(1) | O(1) | O(1) | Linked List |
| ArrayDeque | O(1) | O(1) | O(1) | O(1) | Array |
| ConcurrentLinkedQueue | O(1) | O(1) | O(1) | O(n) | Linked List |
| ArrayBlockingQueue | O(1) | O(1) | O(1) | O(1) | Array |
| PriorityBlockingQueue | O(log n) | O(1) | O(log n) | O(1) | Priority Heap |
| SynchronousQueue | O(1) | O(1) | O(1) | O(1) | None |
| DelayQueue | O(log n) | O(1) | O(log n) | O(1) | Priority Heap |
| LinkedBlockingQueue | O(1) | O(1) | O(1) | O(1) | Linked List |
Map
| Collection |
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 Table |
| ConcurrentSkipListMap | O(log n) | O(log n) | O(1) | Skip List |