Chaper 2 Basics of Algorithm Analysis Flashcards
1
Q
What two things does analyzing an algorithm include?
A
Resource requirements when it comes to space and time.
2
Q
How do you normally express resource requirements?
A
As how the required resources scale with input size.
3
Q
What is meant by a problem being easier than another?
A
That there exist algorithms such that one is faster, often with respect to input size.
4
Q
What is meant by the time complexity of a given algorithm?
A
The algorithm’s running time for every instance. It is often simplified to a running time for every instance size n.
5
Q
What is meant by worst-case and average-case running time?
A
Worst case: The largest running time for an instance of a given size n.
Average case: The average running time for every instance size n.
6
Q
A
