Final Exam Flashcards
running times of insertion sort
o Best case: O(n)
o Worst case: O(n^2)
o Average case: O(n^2)
running times of bubble sort
o Best case: O(n)
o Worst case: O(n^2)
o Average case: O(n^2)
running times of heap sort
o Best case: O(n log n)
o Worst case: O(n log n)
o Average case: O(n log n)
running times of merge sort
o Best case: O(n log n)
o Worst case: O(n log n)
o Average case: O(n log n)
recurrence relationship for merge sort
T(n) = 2T(n/2) + O(n) n > 1
O(1) n = 1
running times for quick sort
o Best case: O(n log n)
o Worst case: O(n^2)
o Average case: O(n log n)
running time and recurrence for quick sort with a 8 to 3 split
RT = O(n log n)
T(n) = T(8n/11) + T(3n/11) + O(n) n > 1
O(1) n = 1
recurrence relationship for worst case of quick sort
T(n) = T(n-1) + O(n) n > 1
O(1) n = 1
Djikstras priority queue implemented with array: running times for insert, decrease key, and delete min
insert: O(1)
decreasekey: O(1)
deletemin: O(n)
Djikstras priority queue implemented with binary heap: running times for insert, decrease key, and delete min
insert: O(log n)
decreasekey: O(log n)
deletemin: O(log n)
running times for search, insert, and delete on regular binary search tree with n nodes
O(h) where h is the height of the tree . . . or O(n)
running times for search, insert, and delete in a red-black tree with n internal nodes
O(log n)
running time for topological ordering (linearization) algorithm
O(|V| + |E|)
running time for longest common string
O(n * 2^m)
running time for edit distance
O(n * m)
definition for Asymptotic / Big O Notation
f(n) = O(g(n)) if there exist positive constants c and n0 such at 0 <= f(n) <= c*g(n) for n >= n0
worst case / lower bound
height of heap with n nodes
O(log n)
height of red-black tree with n internal nodes
O(log n)
definition of master theorem
T(n) = aT(n/b)+(n^d) for a > 0, b > 1, d >= 0
then,
O(n^d) if d > log_b a
T(n) = O(n^d * log n) if d = log_b a
O(n^log_b a) if d < log_b a
definition of big omega notation
best case RT / lower bound
definition of big theta notation
is both big O and big omega
True or False: If f(n) = Θ(g(n)) and g(n) = Θ(h(n)), then h(n) = Θ(f(n)).
True
True or False: If f(n) = O(g(n)) and g(n) = O(f(n)) then f(n) = g(n).
False
True or False: 𝑛/100 = Ω(n).
True
Properties of min heap
Complete tree where every parent must be of lower value than its children
Properties of red-black tree
- Every node is colored red or black.
- The root is black.
- Every “leaf” (the sentinel) is colored black.
- Both children of a red node are black.
- Every simple path from a child of node X to a leaf has the same number of black nodes.
Under what condition will the Bellman-Ford algorithm not work?
When the graph contains a negative cycle
what is black height for a RBT?
number of black nodes in a path (must be the same for all paths)
running time of Kruskal’s
O( |E| * log|V|)
running of time of Primm’s as binary heap, as array
binary heap: O(|E| + |V|) * log|V|),
array: O(|E|^2)
* same as running time of Djikstras
running time of Djikstras: binary heap and array
binary heap: O(|E| + |V|) * log|V|),
array: O(|V|^2)
running time of Bellman-Ford
O(|V| * |E|)
running time of DFS
O(|V| + |E|)
running time of BFS
O(|V| + |E|)
