Complexity Flashcards
Define an algorithm
A computational process that is guaranteed to terminate and return a result for all legal inputs
What is a monte carlo algorithm?
An algorithm that uses random sampling to get a non random answer
What are the four core categories that can be used to distinguish algorithms?
Control
Finiteness
Pre conditions
Determinism
What is memoisaiton?
Optimization technique used to speed up algorithms by storing results of expensive function calls
What is the trade off that lies at the heart of complexity?
Space versus Speed
What are heuristics?
A technique designed for approximating a solution when classic methods fail or are too slow
Describe the heuristic for finding a median
Pick the first three numbers off the list
Sort them, and return the middle one
What are the three cases for running time?
Worst case
Best case
Average case
What does asymptotic mean?
As n tends towards infinity
What is the best case for sorting?
Happens when the list is already sorted
What is the worst case for sorting?
When the list is perfectly reverse sorted
Describe the O notation
Captures the most dominant term
Typically a function of n
What does the O notation do?
Bounds the expression describing the time complexity
How can we simplify the function f(n)
- Discard all the terms except the one that grows fastest
- Discard any constant terms
What is the problem size for a FSA?
Length of the input stream
