| Data Structure | Time Complexity | Space Complexity | |||
|---|---|---|---|---|---|
| Worst | Worst | ||||
| Access | Search | Insertion | Deletion | ||
| Array | O(1) |
O(n) |
O(n) |
O(n) |
O(n) |
| Stack | O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| Queue | O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| Singly-Linked List | O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| Doubly-Linked List | O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| Hash Table | N/A |
O(n) |
O(n) |
O(n) |
O(n) |
| Binary Search Tree | O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
| B-Tree | O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
| AVL Tree | O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
| Array Sorting Algorithms | |||||
| Quicksort | Ω(n log(n)) / O(n^2) |
O(log(n)) |
|||
| Heapsort | O(n log(n)) |
O(1) |
|||
| Mergesort | O(n log(n)) |
O(n) |
|||
| Counting Sort | O(n+k) |
O(k) |
|||
| Selection Sort | O(n^2) |
O(1) |
|||
| Binary search algorithm(Only sorted Arr) | O(log(n)) |
O(1) |
|||
| Graph Algorithms | |||||
| Tree traversal | O(N + N-1) |
O(N) |
|||
| Dijkstra | O(E+VlogV) |
O(V^2) |
|||
| Breadth first search | O(E+V) |
O(V) |
|||
| Depth first search | O(E+V) |
O(V) |
|||
| Bellman Ford | O(EV) |
O(V) |
|||