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

Source

BFS

procedure BFS(G, root) is
    let Q be a queue
    label root as explored
    Q.enqueue(root)
    while Q is not empty do
        v := Q.dequeue()
        if v is the goal then
            return v
        for all edges from v to w in G.adjacentEdges(v) do
            if w is not labeled as explored then
                label w as explored
                w.parent := v
                Q.enqueue(w)

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

Dijkstra

function Dijkstra(Graph, source):
  
    for each vertex v in Graph.Vertices:
        dist[v] ← INFINITY
        prev[v] ← UNDEFINED
        add v to Q
    dist[source] ← 0

    while Q is not empty:
        u ← vertex in Q with min dist[u]
        remove u from Q
        
        for each neighbor v of u still in Q:
            alt ← dist[u] + Graph.Edges(u, v)
            if alt < dist[v]:
                dist[v] ← alt
                prev[v] ← u

    return dist[], prev[]

Source

Big O Notation

Adapted from Big-O Cheat Sheet

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)
Dijkstra
A*			O(E) = O(b^d)	O(V) = O(b^d)