Finding Faster Algorithms Flashcards
1
Q
exponentiation vs. faster exponentiation
A
O(n) vs. O(k)
2
Q
What is memoization
A
Intermediate values returned by the function can be memoized, or saved in a cache, for subsequent access
They don’t have to be recomputed!
3
Q
fib vs. fastFib
A
somewhere between O(1^n) and O(2^n) vs. O(n)
4
Q
selection sort vs. quick sort
A
O(n^2) vs. best case O(nlog2(n)) worst case O(n^2)
5
Q
When will quick sort degrade to O(n^2)?
A
When the value at the midpoint is near the largest or smallest value on each call (there will be approximately n subdivisions)
6
Q
Other methods of selecting the pivot element
A
Pick a random element
Pick the median of the first three elements
Pick the median of the first middle and last elements
Pick the median element - not!!! This is an O(n) algorithm
