menu

Algorithm Questions Here
Big O
SortingTypicalΘ(log n)Heap sort, Merge sort, Bubble sort, etc
HashingInsertionO(1)Add to beginning
DeletionSearch time + O(1)Using doubly linked list
SearchWorst: O(n)
Expected: Θ(1 + α)
worst if all keys are in one slot
α = n/m = #keys/#slots
HeapsTypicalO(log n)
buildMaxHeapO(n)
Red Black TreesTypicalO(log n)Balanced height is at most log n
Find/UnionQuick FindO(1)
UnionO(log n)
Adjacency Representation
 ListSearchWorst: Θ(V)
StorageΘ(V + E)
 MatrixStorage SpaceΘ(V2)
BFS, DFS, SCCTotal RuntimeΘ(V + E)V = vertex set, E = edge set
Kruskal's AlgorithmTotalO(E logV) → O(logV)Notice |E| ≤ |V|2sup>
Prim's AlgorithmTotalO(E logV)with binary heaps
O(E + V logV) with Fibonacci heaps
Dijkstra's AlgorithmTotalO(E logV)with binary heaps
O(E + V logV) with Fibonacci heaps
Gale ShapleyTotalO(n2)Best case Ω(n)
Bipartite MatchingRuntimeO(nm)
Weighted Interval SchedulingMemoizationO(n logn)O(n) if presorted
Dynamic ProgrammingBacktrackingO(n)Usually, given each backtrack has constant time.
Needleman-WunschTotalΘ(mn)m, n are sequence lengths
SpaceΘ(mn)
Optimal Value SpaceΘ(m + n)Still with Θ(mn) runtime, but we cannot recover optimal alignment
Bellman-FordTotalO(VE)
Knapsack ProblemPossibleΘ(nW)W is integer weight
SpaceΘ(nW)