Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
26 Cards in this Set
- Front
- Back
|
Insertion Sort Time Complexity |
WORST-CASE: array is in reverse order O(n^2) BEST-CASE: array is sorted O(n) |
|
|
Insertion Sort Decision Tree |
|
|
|
Merge-Sort Time Complexity |
Θ(n log(n)) |
|
|
Merge-Sort Decision Tree |
|
|
|
Parallel sum |
#pragma omp parallel for default(shared) reduction(+:subsum) |
|
|
Quicksort Time Complexity |
BEST CASE: Divide into equal subarrays Θ(nlogn)
WORST-CASE: if the list is already sorted O(n^2) |
|
|
HEAP-INCREASE-KEY, (MAX)-HEAPIFY, EXTRACT-MAX and INSERT Time Complexity |
O(log n) |
|
|
HEAPSORT Time Complexity |
O(n log n) |
|
|
BUILD-(MAX)-HEAP |
O(n) |
|
|
Select Time Complexity |
The expected running time: O(n) The worst-case running time: O(n^2) |
|
|
CHAINED-HASH_SEARCH(T, k) & CHAINED-HASH-DELETE(T, x) |
O(n) |
|
|
CHAINED-HASH-INSERT(T, x) |
O(1) |
|
|
BST dynamic set operations |
O(h) |
|
|
2-3 Tree Operations Time Complexity |
O(log n) |
|
|
Basics of dynamic programming
|
(1) Optimal Substructure: an optimal solution to the problem exhibits optimal substructures: an optimal solution to the problem contains within it optimal solutions to subproblems. (2) Overlapping Subproblems: when a recursive algorithm for the problem revisits the same subproblems over and over |
|
|
DFS Time Complexity |
Θ(n + m) |
|
|
BFS Time Complexity |
O(n + m) |
|
|
Union by rank |
O(m log n) m = total number of operations n = total number of make set operations |
|
|
Path Compression |
each node on the root find path point directlyto the root
|
|
|
Path Compression & Union by Rank Time Complexity |
O(m α(m, n)) |
|
|
Prim Time Complexity |
O(m log n)
|
|
|
Kruskal Time Complexity |
O(m log n) |
|
|
cut |
is a partition of vertices into disjoint sets V and S − V. |
|
|
Edge Crosses cut |
if one endpoint is in S and the other is in V-S |
|
|
cut respects A |
if and only if no edge in A crosses the cut |
|
|
light edge |
if and only if its weight is minimum over all edges crossing the cut for a given cut |
