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
Source
DFS
procedure DFS(G, v) is
label v as discovered
for all directed edges from v to w that are in G.adjacentEdges(v) do
if vertex w is not labeled as discovered then
recursively call DFS(G, w)
procedure DFS_iterative(G, v) is
let S be a stack
S.push(v)
while S is not empty do
v = S.pop()
if v is not labeled as discovered then
label v as discovered
for all edges from v to w in G.adjacentEdges(v) do
S.push(w)
Source
Big O Notation
Data Structure Operations
| 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
|
Array Sorting Algorithms
| 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)
|
Tree Traversing Algorithms
| Data Structure |
Time Complexity |
Space Complexity |
Notes
|
| Best |
Average |
Worst
|
| BFS |
|
|
O(V + E) = O(b^d) |
O(V) = O(b^d)
|
| DFS |
|
|
O(b^d) |
O(E) = O(bd)
|
| DFS, recursive |
|
|
O(V + E) |
O(V)
|