O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
Data Structures
Arrays / Dynamic Arrays
| Operation |
Time |
Space |
| Access |
O(1) |
O(n) |
| Search |
O(n) |
|
| Insert (end) |
O(1) amortized |
|
| Insert (middle) |
O(n) |
|
| Delete |
O(n) |
|
Linked Lists (Singly / Doubly)
| Operation |
Time |
Space |
| Access |
O(n) |
O(n) |
| Search |
O(n) |
|
| Insert (head) |
O(1) |
|
| Insert (tail) |
O(1)* |
|
| Delete |
O(1)* |
|
- if pointer/reference available
Stack / Queue / Deque
| Operation |
Time |
Space |
| Push / Pop |
O(1) |
O(n) |
| Peek |
O(1) |
|
HashMap / HashSet
| Operation |
Avg Time |
Worst |
Space |
| Insert |
O(1) |
O(n) |
O(n) |
| Delete |
O(1) |
O(n) |
|
| Search |
O(1) |
O(n) |
|
Binary Search Tree (BST)
| Operation |
Avg |
Worst |
Space |
| Search |
O(log n) |
O(n) |
O(n) |
| Insert |
O(log n) |
O(n) |
|
| Delete |
O(log n) |
O(n) |
|
Balanced BST (AVL / Red-Black)