Reading...
Play button
Play button
Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
21 Cards in this Set
- Front
- Back
|
What are the qualities of a good algorithm?
|
1) correct
2) efficient |
|
|
What factors constitute efficient?
|
mostly running time, but space, memory, and communication can also be considered
|
|
|
What is the running time of an algorithm usually based on?
|
worst case scenario
|
|
|
When would you want an average running time instead of worst case?
|
when the worst case is a rare of very rare occurrence
|
|
|
What additional factors influence absolute running time?
|
size of input, machine hardware,etc ...
|
|
|
What can you ignore when figuring out a running time to an algorithm?
|
-machine dependent constants
-lower order terms |
|
|
What does the RAM Machine Model assert?
|
primitive operations (+ - / *, data movement, comparisons, function calls, etc ...) are constant time, so ignore them
|
|
|
What is the calculus definition of big-Theta?
|
the limit of the algorithm as n approaches infinity is a constant
|
|
|
What are the different running time notations we discussed in class?
|
big O
big Omega big Theta |
|
|
What is the definition of big-O?
|
a function is big-O if and only if there exists two constants c > 0 and n0 > 0, such that for all n0, f(n) <= c * g(n)
|
|
|
What is another way to think of big-O?
|
an algorithm has an upper bound
|
|
|
What is another way to think of big-Omega?
|
an algorithm has a lower bound
|
|
|
What is another way to think of big-theta?
|
an algorithm has both an upper bound and a lower bound
|
|
|
What is the definition of big-Omega?
|
an algorithm is big-Omega if and only if there are two constants such that c > 0 and n0 > 0, such that for all n > n0, f(n) >= c * g(n)
|
|
|
We have f(n) = O(g(n)). What is a way to prove this is true?
|
if g(n) = OMEGA(f(n))
|
|
|
What is the definition of big-Theta?
|
an algorithm is big-Theta if and only if there are three constants c1, c2 and n0 > 0 such that for all n > n0, c2 * g(n) <= f(n) <= c1 * g(n)
|
|
|
What is a way to prove a function is big-theta?
|
if f(n) = O(g(n)) and f(n) = OMEGA(g(n))
|
|
|
What is the calculus definition of big Omega?
|
the limit of the algorithm as n approaches infinity is infinity
|
|
|
What is the calculus definition of big O?
|
the limit of the algorithm as n approaches infinity is zero
|
|
|
When thinking of the calculus definition of big-O, Theta, and Omega, what are you taking the limit of?
|
f(n) / g(n)
|
|
|
What are the steps to divide and conquer?
|
1) divide the problem into a smaller number of sub-problems
2) solver the smaller sub-problems recursively 3) combine the solutions to get the final answer |
