Section 1
Preview this deck
Array contains(v) complexity
Front
| 5 | 0 | ||
| 4 | 0 | ||
| 3 | 0 | ||
| 2 | 0 | ||
| 1 | 0 |
Active users
2
All-time users
3
Favorites
0
Last updated
1 year ago
Date created
Mar 1, 2020
Cards (124)
Section 1
(50 cards)
Array contains(v) complexity
O(n)
LinkedList get(int i) complexity
O(n)
quick sort worst case space
O(n)
binary search
given a sorted array b, store in i index of v i = -1; k = b.length; while (i != k-1) { int m = (i + k)/2; if (b[m] <= v) { i = m; } else { k = m;}}
insertion sort stability
Yes
interfaces consist of:
public abstract methods
LinkedList contains(v) complexity
O(n)
basic step
a step whose time it takes to evaluate does not depend on the size of the data on which it operates; takes constant time
selection sort average complexity
O(n^2)
quick sort stability
No
interface comparable
returns a negative int, 0, or positive int as this object is less than, equal to, or greater than ob; class must implement: int compareTo(T ob);
4 Loopy Questions
1. Does it start right? Does the initialization make the invariant true? 2. Does it end right? Is the postcondition .true upon termination? 3. Does the repetend make progress toward termination? 4. Does the repetend keep the invariant true?
merge sort space complexity
O(n)
linear search
given an array b, it is known that value v is in it; store in k the index of the first occurrence of v in b k = 0; while (b[k] != v) { k = k+1;} return k; given an array b, unknown whether value v is in it; store in k the index of the first occurrence of v in b i = -1; k= b.length(); while (i+1<k) { if (b[i+1] == v) { return i+1; }
interface iterable
implementing this interface allows an object to be the target of a for-each loop; requires declaring method iterator method = iterator() ex. public class Stack<E> implements Iterable<E> { public abstract Iterator<T> iterator();
merge sort worst-case complexity
O (n log n)
quick sort worst-case complexity
O(n^2)
linear search average complexity
O(n)
merge sort
if (h >= k) { return; } int e = (h+k)/2; mergeSort(b, h, e); mergeSort(b, e+1, k); merge(b, h, e, k);
merge sort stability
Yes
interface iterator
an object that provides methods to write a loop to enumerate & process each element methods = hasNext() and next() - hasNext(): returns boolean for if there is a next item - next(): always starts with call of hasNext(); return next variable - constructor must initialize field n to the index
quick sort
int h1=h; int k1=k; while (b[h1..k1] has more than 1 element) { int j = partition(b, h1, k1); if (b[h1..j-1] is smaller than b[j+1..k1]) { QS(b, h, j-1); h1 = j+1; } else { QS(b, j+1, k1); k1 = j-1; }
LinkedList poll() complexity
O(n)
Array add() complexity
O(n)
List<T> methods
get(int), indexOf(int), add(int, T)
Map<K,V> methods
put(k,v), get(object)
insertion sort space complexity
O(1)
binary search average complexity
O(log n)
insertion sort
k = 0; while (k != b.length) { j = k; while (k > 0 && b[k] < b[k-1]) { swap b[j-1] and b[j]; j = j-1; } k = k + 1; }
quick sort average complexity
O(n log n)
heap sort average complexity
O(n log n)
Array get(int i) complexity
O(1)
quick sort space complexity
O(log n)
insertion sort worst-case complexity
O(n^2)
when time complexity is log n
1. when the variable that is within the loop guard double with every iteration 2. recursive problems where n gets split in half each iteration
heap sort worst-case complexity
O(n log n)
heap sort
Make array into a max heap, then poll, and repeat for (int k = 1; k < b.length; k = k+1) { bubbleUp(b,k); } for (int k = b.length-1; k > 0; k = k-1) { swap b[0] and b[k]; bubbleDown(b,k); }
quick sort partition average complexity
O(n)
quick sort partition
j = h; t = k; while (j < t) { if (b[j+1} <= b[j]) { swap b[j+1] and b[j]; j = j+1; } else { swap b[j+1] and b[t]; t = t-1; }}
insertion sort average complexity
O(n^2)
selection sort stability
No
selection sort space complexity
O(1)
merge sort average complexity
O(n log n)
linear search worst-case complexity
O(n)
Collection<T> methods
add(T), contains(object), isEmpty(), remove(object), size(), etc.
binary search worst-case complexity
O(log n)
selection sort worst-case complexity
O(n^2)
selection sort
k = 0; while (k != b.length) { j = k+1; i = k; for (j = k+1; j < b.length; j = j+1) { if (b[j] < b[i]) { i = j; } swap b[k] and b[i]; k = k+1; }
definition of big-O
function f(n) is in set O(g(n)) if there exists a positive constant c and N where for all n >= Nm f(n) <= c*g(n) - O(g(n)) bounds the function f(n) - f(n) grows like g(n) or slower
LinkedList add(v) complexity
O(1)
Section 2
(50 cards)
HashSet add(v) complexity
O(1)
Adjacency Matrix best for:
dense graphs
recursive DFS space complexity
O(V)
iterative DFS uses:
stack
Binary Search Tree
a binary tree with the property that for all parent nodes, the left subtree contains only values less than the parent, and the right subtree contains only values greater than the parent.
sorted LinkedList contains(v) complexity
O(n)
Adjacency Matrix find an edge complexity
O(1)
tree depth
length of path from root to node
Adjacency Matrix space complexity
O(|V|^2)
preorder
process root, then left, then right (stick on left)
Heap add(v) complexity
O(log n)
iterative DFS & BFS list time complexity
O(V+E)
Heap poll() complexity
O(log n)
sorted LinkedList peek() complexity
O(1)
Adjacency List visit all edges complexity
O(|V| + |E|)
BFS
Queue q = new Queue(); q.add(u); while (q is not empty) { u = q.remove(); if (u is not visited) { visit u; for each (u,v) { if (v not encountered) { mark v as encountered; q.add(v); }}}
iterative DFS & BFS matrix time complexity
O(V^2)
Heap peek() complexity
O(1)
Balanced BST poll() complexity
O(log n)
Adjacency List find an edge complexity
O(|V| + |E|)
Balanced BST peek() complexity
O(log n)
heap must:
be a complete binary tree and have a heap-order (max-heap or min-heap)
Adjacency List best for:
sparse graphs
HashSet get(int i) complexity
O(1)
BFS uses:
queue
Adjacency Matrix visit all edges complexity
O(|V|^2)
Binary Search Tree add(v) complexity
O(height)
Adjacency List space complexity
O(|V| + |E|)
Binary Tree contains(v) complexity
O(n)
max number of total nodes in binary tree
2^(h+1) -1
sorted LinkedList get(int i) complexity
O(n)
recursive DFS list time complexity
O(V+E)
complete binary tree
every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
sorted LinkedList poll() complexity
O(1)
sorted LinkedList add(v) complexity
O(n)
tree height
length of longest path from the root to a leaf
iterative DFS
Stack s= new Stack(); s.push(u); while (s is not empty) { u = s.pop(); if (u not visited) { visit u; } for each edge (u,v) { s.push(v); }}
recursive DFS matrix time complexity
O(V^2)
DFS concept
search entire paths at a time; like following a maze
Balanced BST search complexity
O(log n)
BFS concept
search each possibility at a level before moving on; like a search party fanning out
BST search complexity
O(n)
min number of total nodes in binary tree
height + 1
Binary Search Tree contains(v) complexity
O(height)
inorder
process left, then root, then right (stick down)
postorder
process left, then right, then root (stick on right)
LinkedList peek() complexity
O(n)
max number of nodes at depth d in binary tree
2^d
Balanced BST add(v) complexity
O(log n)
HashSet contains(v) complexity
O(1)
Section 3
(24 cards)