Quiz 1 Flashcards
If f(n) is in O(kg(n)) for any constant k>0 then
f(n) is in O(g(n))
If f(n) is in O(n) and g(n) is in O(h(n)) then…
f(n) is in O(h(n))
If f1(n) is in g1(n) and f2(n) is in g2(n) then f1(n) + f2(n) is
in O(max(g1(n),g2(n)))
If f1(n) is in O(g1(n)) and f2(n) is in O(g2(n)) then f1(n)f2(n) is
in O(g1(n)g2(n))
Growth ratefastest->slowest
constant, multi log, log, log squared, log^k, linear, nlogn, N^2, N^3, c^N
Form for an algebraic spec
adt NAME
uses \_\_\_\_\_
operations:
preconditions
axiomsBig O
T(N) is (f (N)) if there exists c, n such that T(N) = n. (upper bound)
Big Omega
T(N) is Omega(g(N)) if there exists c, n such that
T(N) >= cg(N) for all N >= n. (lower bound)
Big Theta
T(N) is Theta(h(N)) if and only if T(N)=(h(N)) and
T(N) = Omega(h(N)). (tight bound)
Little o
T(N) is o(p(N)) if for all c there exists n such that
T(N) < cp(N) when N > n. (loose upper bound: T(N)=(p(N))
but T(N) 6 != (p(N)) )
Array - indexing complexity
O(1)
Array - search
O(n)
Dynamic Array - indexing
O(1)
Dynamic Array - Search
O(n)
Dynamic Array - Insertion
O(n)
Dynamic Array - deletion
O(n)
Singly Linked List - indexing
O(n)
Singly Linked List - Search
O(n)
Singly Linked List - insertion
O(1)
Singly Linked List - deletion
O(1)
Doubly Linked List - indexing
O(n)
Doubly Linked List - Search
O(n)
Doubly-Linked List - insertion
O(1)
Doubly-Linked List - deletion
O(1)
Binary Search Tree - Indexing
O(log(n)), average. O(n) worst
Binary Search Tree - Search
O(log(n)), average. O(n) worst
Binary Search Tree - Insertion
O(log(n)), average. O(n) worst
Binary Search Tree- deletion
O(log(n)), average. O(n) worst
Splay Tree - Search
Always O(log(n))
Splay Tree - Insertion
Always O(log(n))
Splay Tree - deletion
Always O(log(n))
AVL Tree- Search
Always O(log(n))
AVL Tree- insertion
Always O(log(n))
AVL Tree - deletion
Always O(log(n))
Binary Search
O(log(n)) always on sorted array of n elements
Bubble Sort
Best, O(n).
Worst, O(n^2).
Average, O(n^2)
Merge Sort
always O(nlog(n))
Insertion Sort
best O(n). average O(n^2) worst O(n^2)
Bag Structure methods
add, remove, contains, size, clear, isEmpty
Set Structure Methods
add, remove, size, isEmpty, contains, union, intersect
Queue Structure Methods
enqueue, dequeue, front,
Stack Structure Methods
push, pop, peek
Tree
update, insert, delete, getValueFromKey
amortized analysis of efficiency
method of anallyzing algorithms that consider the entire sequence of operation of the program. Its bigO notation.
binary trees - how many children
2 most
BST property
the key in any node is larger than all keys in that nodes left subtree and smaller than all keys in the right subtree.
how many nodes fit in each level
2^i where i is the level
how many nodes can a tree with h levels store
(2^h) - 1
depth of root
0
depth of node generally
1 + depth of parent
heigh of tree
leaves have 0.
Generally - 1 + heigh of children
AVL Tree condition
every node in tree, heigh of left and right differ by <= 1
breadth first print
Starts at root, prints left to right before going to next level down
depth first preorder
visit current node, then entire left tree, then entire right subtree
depth first postorder
visit entire left, then entire right tree - then current node.
Binary Search
O(logn)
find place to check binary search
(start +end )/2
deque
removeal and insertion at both ends “double ended queue”
bubble sort
bubble biggest rightward. O(N^2)
selection sort
find smallest each time O(N^2)
insertion sort
swap adjacent each time two insert O(N^2)
merge sort
O(NlgN)
heap sort
bottum up build + N removals O(NlgN)
quick sort time complexity
worst O(N^2) best O(NlgN)
bottom up heap build time complexity
O(N)
insert/removemax for heap
o(lgN)
degree
number of incident edges
adjacent edges
edge between u and v exists
multigraph
a graph that can have repeated edges
Cycle
a path of length >= whose first and last are the same
connected graph G
there is a path in g from every vertex to everyother
acyclic graph
a graph with no cycles
tree
an acyclic connected graph
forrest
a disjoint set of trees
subgraph of G
subset of graph G’s edges and verts
spanning tree of a connected graph G
a subgraph that contains all of G’s verticies and is a single tree
summ of all degrees in normal graph
2M
undirected graph
M<= (N(N-1)/2)
directed graph M
M <= N(N-1)
connected graph M
M >= N -1
tree M
M = N - 1
forrest M
M <= N - 1
graph small scale operations
getnumVerts, getNumEdges, boolean adjacent(u,v), neighbors(V), int degree (v), boolean incident(v,e), bolean connected(u,v)
graph large scale operations
depth first search, breadth first search, find spanning tree, shortest path between verts, connected components, isConnected, isTree, hamiltonianTour, Eulerian Path
Hamiltonian Tour
visit every vertex exactly 1x
Eulerian Path
visit all edges exactly 1x
adjacency matrix
store a v x v boolean array that is true exactly when an edge v-w exists
array of edges
stores a list of edge objects where each one has two int instance variables
adjacency list
store a vertex index array of lists of vertices. VertexArray[i] is linked list of verticies adjacent to vertex[i]
Topological Sort
order vertices so that each v comes earlier in list than any other vertex to which an edge leads from v
strongly connected graph
are all vertex pairs(v,w) s.t. v is reachable from w and w is reachable from v
single source unweighted shortest path
O(N+M). Set all distances to infinity Set all previous to null. Set source to 0. Begin BFS: Q.enqueue(s) While Q is not empty: v = Q.dequeue() for all u in neighbors(v) with prev[u]==null dist[u] = dist[v] + 1 prev[u] = v Q.enqueue(u)
Complexity of Dijkstras Algorithm
O(MlgN) with adaptable heap
Topological Sort time complexity
O(N+M) to compute indegrees
O(N+M) to determine ordering
O(N+M) total
