Term
|
Definition
Best n
Avg n squared
Worst n squared |
|
|
Term
|
Definition
Best n
Avg n squared
Worst n squared |
|
|
Term
|
Definition
|
|
Term
|
Definition
|
|
Term
|
Definition
Best n log n
Avg n log n
Worst n squared |
|
|
Term
|
Definition
|
|
Term
|
Definition
| bubble, insertion, merge, radix |
|
|
Term
|
Definition
|
|
Term
|
Definition
| bubble, insertion, selection, quick |
|
|
Term
|
Definition
| one that maintains the order (from unsorted to sorted) of entries with the same key |
|
|
Term
| what is an in-place sort? |
|
Definition
| one that uses a constant and limited amount of memory when executed |
|
|
Term
|
Definition
| one that sorts as it is given each entry as opposed to those that are given all entries at once |
|
|
Term
|
Definition
|
|
Term
|
Definition
| a connection between two nodes |
|
|
Term
|
Definition
| shortest path unweighted graph (breadth-first search) |
|
|
Term
|
Definition
| connectivity - just find a path between 2 vertices (depth-first search) |
|
|
Term
|
Definition
| shortest path between two vertices in a weighted graph |
|
|
Term
|
Definition
uses disjoint set data structure. looks at all edges simultaneusly and
adds the least weight edge that doesn't create a cycle. |
|
|
Term
| Running times of operations on a Disjoint Set |
|
Definition
|
|
Term
|
Definition
|
|
Term
|
Definition
mn
but can be improved to m+n |
|
|
Term
|
Definition
mn
but m+n with a well behaving hash function |
|
|
