FINAL - Running Times Flashcards
1
Q
Integer multiplication
A
n^lg 3 (3 multiplication subproblems)
2
Q
Strassen’s algorithm
A
n^lg 7 (7 multiplication subproblems!)
3
Q
Maximum subarray
A
n lg n (2T(n/2) + n)
4
Q
Heap Sort
A
n lg n (do lg n heap deletion n times!)
5
Q
Heap Insertion
A
lg n
6
Q
Heap Deletion
A
lg n
7
Q
Heap Deletion best case
A
O(1)
8
Q
Bottom-up heap construction
A
n
9
Q
MCM
A
n^3
10
Q
BFS
A
O(V + E)
11
Q
DFS
A
O(V + E)
12
Q
Topological sort
A
O(V + E), since DFS is the implementation mechanism
13
Q
Strongly-Connected Components
A
O(V + E), since running DFS 2x is the implementation!
14
Q
Prim’s algorithm
A
O(V + E log V)
15
Q
LCS
A
O(n*m)
