Algorithm Questions Here
##### Big O
 Sorting Typical Θ(log n) Heap sort, Merge sort, Bubble sort, etc Hashing Insertion O(1) Add to beginning Deletion Search time + O(1) Using doubly linked list Search Worst: O(n)Expected: Θ(1 + α) worst if all keys are in one slotα = n/m = #keys/#slots Heaps Typical O(log n) buildMaxHeap O(n) Red Black Trees Typical O(log n) Balanced height is at most log n Find/Union Quick Find O(1) Union O(log n) Adjacency Representation List Search Worst: Θ(V) Storage Θ(V + E) Matrix Storage Space Θ(V2) BFS, DFS, SCC Total Runtime Θ(V + E) V = vertex set, E = edge set Kruskal's Algorithm Total O(E logV) → O(logV) Notice |E| ≤ |V|2sup> Prim's Algorithm Total O(E logV) with binary heapsO(E + V logV) with Fibonacci heaps Dijkstra's Algorithm Total O(E logV) with binary heapsO(E + V logV) with Fibonacci heaps Gale Shapley Total O(n2) Best case Ω(n) Bipartite Matching Runtime O(nm) Weighted Interval Scheduling Memoization O(n logn) O(n) if presorted Dynamic Programming Backtracking O(n) Usually, given each backtrack has constant time. Needleman-Wunsch Total Θ(mn) m, n are sequence lengths Space Θ(mn) Optimal Value Space Θ(m + n) Still with Θ(mn) runtime, but we cannot recover optimal alignment Bellman-Ford Total O(VE) Knapsack Problem Possible Θ(nW) W is integer weight Space Θ(nW)