FINAL - Running Times Flashcards
Integer multiplication
n^lg 3 (3 multiplication subproblems)
Strassen’s algorithm
n^lg 7 (7 multiplication subproblems!)
Maximum subarray
n lg n (2T(n/2) + n)
Heap Sort
n lg n (do lg n heap deletion n times!)
Heap Insertion
lg n
Heap Deletion
lg n
Heap Deletion best case
O(1)
Bottom-up heap construction
n
MCM
n^3
BFS
O(V + E)
DFS
O(V + E)
Topological sort
O(V + E), since DFS is the implementation mechanism
Strongly-Connected Components
O(V + E), since running DFS 2x is the implementation!
Prim’s algorithm
O(V + E log V)
LCS
O(n*m)
Insertion sort (avg)
n^2
Quicksort (avg)
n lg n
Quicksort (worst)
O(n^2)
Mergesort
n lg n
Counting sort
n + k
Radix sort
nk
Bucket sort (worst)
O(n^2)
Bucket sort (avg)
n + k
Selection sort
n^2
Making change
n
Maximum Subarray (DP)
n
Rod-cutting
n^2
Kruskal’s algorithm
O(E lg E)
