Programming/Algorithms
Pseudocode
Binary Tree Search
Iterative-Tree-Search(x, key)
while x ≠ NIL and key ≠ x.key then
if key < x.key then
x := x.left
else
x := x.right
end if
repeat
return x
Big O Notation
Adapted from Big-O Cheat Sheet
| Data Structure | Time Complexity | Space Complexity | Notes | |||
|---|---|---|---|---|---|---|
| Average -> Worst | ||||||
| Access | Search | Insertion | Deletion | |||
| Array | Θ(1) -> O(1) | Θ(n) -> O(n) | Θ(n) -> O(n) | Θ(n) -> O(n) | O(n) | |
| Stack | Θ(n) -> O(n) | Θ(n) -> O(n) | Θ(1) -> O(n) | Θ(1) -> O(n) | O(n) | |
| Queue | Θ(n) -> O(n) | Θ(n) -> O(n) | Θ(1) -> O(n) | Θ(1) -> O(n) | O(n) | |
| Linked List | Θ(n) -> O(n) | Θ(n) -> O(n) | Θ(1) -> O(n) | Θ(1) -> O(n) | O(n) | |
| Double Linked List | Θ(n) -> O(n) | Θ(n) -> O(n) | Θ(1) -> O(n) | Θ(1) -> O(n) | O(n) | |
| Hash Table | N/A | Θ(1) -> O(n) | Θ(1) -> O(n) | Θ(1) -> O(n) | O(n) | |
| Binary Search Tree | Θ(log(n)) -> O(n) | Θ(log(n)) -> O(n) | Θ(log(n)) -> O(n) | Θ(log(n)) -> O(n) | O(n) | |
| B Tree | Θ(log(n)) -> O(log(n)) | Θ(log(n)) -> O(log(n)) | Θ(log(n)) -> O(log(n)) | Θ(log(n)) -> O(log(n)) | O(n) | Self-balancing |
| Data Structure | Time Complexity | Space Complexity | Notes | ||
|---|---|---|---|---|---|
| Best | Average | Worst | |||
| Bubble Sort | Ω(n) | Θ(n^2) | O(n^2) | O(1) | |
| Quicksort | Ω(n log(n)) | Θ(n log(n)) | O(n^2) | O(log(n)) | |
| Mergesort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) | O(n) | |
| Insertion Sort | Ω(n) | Θ(n^2) | O(n^2) | O(1) | |
| Timsort | Ω(n) | Θ(n log(n)) | O(n log(n)) | O(n) | Combination of Mergesort and Insertion Sort made for Python |
| Heapsort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) | O(1) | |