Oh, my!
This Greek letter describes a lower bound on the asymptotic running time of an algorithm.
What is Omega?
A type of tree traversal that lists the elements in order.
What is inorder traversal?
This abstract data type efficiently returns an element of highest (or lowest) priority.
What is a priority queue?
A property of hash functions that should be minimized.
What are collisions?
This component of the memory architecture affects how efficiently data can be read into the CPU, making it faster (generally) to read successive memory locations.
What is the cache?
This function is upper bound on the asymptotic running time of most general purpose sorting algorithms.
What is (n log n)?
The asymptotic upper bound on the height of a balanced BST with n nodes.
What is
O(log n)
The relationship of the element at index 2i to the element at index i in an array-based heap.
What is the left child?
A function called to reduce the size of the hash code to suit the hash table length.
What is a compression function?
When implementing an ordered list ADT, this data structure would provide faster search times.
What is an array?
It is not always the case that an O(n) algorithm is faster than an O(n2) algorithm. This is because Big-Oh notation discards these non-varying numeric values.
What are constants?
For an AVL tree, the condition that the heights of the subtrees of a vertex v differ by at most one.
What is the height-balance property?
The elements at indices
floor(n/2)+1
to n in an array based heap.
What are the leaves or external nodes?
The ratio of the number of elements in a hash table to the hash table size; if it is too large, performance will suffer.
What is the load factor?
The preferred data structure when implementing an ordered map ADT.
What is a balanced BST?
This function is a tight asymptotic upper bound on
T(n) = 3 n^2 + 7 n log n + 1
What is a quadratic?
n^2
The property of a red-black tree that all external nodes have the same number of black ancestors.
What is the depth property?
The element at index n is moved to index 1.
What replaces the min (or max) value after a call to extract-min (or extract-max)?
A method for managing collisions in which if the location at index h of the hash table is already used, the indices at location (h + i2) mod N are checked for a range of i values.
What is quadratic probing?
In mathematical induction, the statement that the property to be proved is assumed to hold for some specific but arbitrary range of integer values.
What is the inductive hypothesis?
A type of asymptotic analysis that divides the cost of a few expensive operations among many cheaper operations.
What is amortized analysis?
The simplest operation that can resolve a double red in a red-black tree; it can only be used when the parent and both children are red.
What is a recoloring?
The running time of Union(x, y) in a binomial heap.
What is O(1)?
A function which when applied to the output x of a hash code computes
h = (a cdot x + b) mod N
What is the MAD compression function?
A method of optimizing disjoint set forests in which when returning from the recursive calls in Find-Set, the parent of each visited node is set to the root node.
What is path compression?