| Running time where the program gets slightly slower as N grows; commonly occurs in programs that solve a problem by transforming it into a smaller problem. |
| |
| Measure of an algorithm’s performance on the worst possible input. (2 words) |
| |
| An algorithm’s performance under optimal conditions. (2 words) |
| |
| As input size increases, the running time of an algorithm _________. |
| |
| Relationship between input length and number of steps for an algorithm. |
| |
| Running time where when N doubles, the running time is squared. |
| |
| The methods of run-time analysis can also be used for other growth rates, such as ______ usage. |
| |
| The _______ cost model assigns a constant cost to every machine operation, regardless of the size of the numbers involved. |
| |
| Many programs are extremely sensitive to _____, and performance could fluctuate wildly depending on it. |
| |
| Running time that is some value to the power of N. |
| |
| A type of analysis that considers the entire sequence of operations, not just those handling input/output, and targets the worst case scenario. |
| |
| When the results of algorithm analysis are an expression consisting of a sequence of decreasing terms (n^2 + n + 1) we care most about the _______ term. |
| |
| A type of analysis which estimates an upper bound for an algorithm based on its complexity for arbitrarily large input. |
| |
| An algorithm is said to be of __________ time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm. |
| |
| If all instructions in a program are executed once, or only a few times, the running time is ________. |
| |
| One step in algorithm analysis is to find the best _____ _____, which could be achieved for the worst input. (2 words) |
| |
| Running time where when N doubles, the running time increases eightfold. |
| |
| The optimal running time for an algorithm that must process N inputs. |
| |
| The notation used to show worst case performance. |
| |
| Measure of an algorithm’s performance on typical input data. (2 words) |
| |
| The determination of the amount of resources (time and storage) needed to execute an algorithm. (2 words) |
| |