Basic Terms Flashcards
1
Q
RAM Model
A
Random Access Machine Model
2
Q
2 Assumptions of the RAM model
A
Steps are executed sequentially, each step is an operation that takes constant time
3
Q
Constant running time
A
O(1) complexity independent of input size
4
Q
logarithmic running time
A
O(log n)
5
Q
linear running time
A
O(n)
6
Q
log-linear running time
A
O(n log n)
7
Q
polynomial running time
A
O(n^c) where c is a constant
8
Q
exponential running time
A
O(c^n) where c is a constant raised to a power based on the input
9
Q
6 classes of complexity in order of worst-case speed
A
constant, logarithmic, linear, log-linear, polynomial, exponential
10
Q
What quality should you look for in a good hash function?
A
Uniform distribution of results, to minimize collisions. Must also be deterministic.
