Week 2: Analysis of Algorithms Flashcards
What are the criteria we can use to compare algorithms? What are the most important ones?
What is complexity of an algorithm? What is space complexity? Time complexity?
What does a complexity function look llike? What can it not look like?
The complexity of an algorithm depends on:
The input itself, not only the size.
What are the three kinds of complexity functions?
Best case complexity
Least amount of resources needed by the algorithm to solve an instance of the problem of size n. (when the number is at the beginning of an array in a search algorithm.
Worst case complexity:
Largest amount of resources needed by the algorithm to solve an instance of the problem of size n.
Average case complexity:
Every instance has its own complexity: find each complexity and find the average
Does the size of the input n have anything to do with worst/best case complexity? I.e, does having a small input n mean best case?
No the best and worst case complexities are independant of the size of input n.
What things do you need to measure the complexity of an algorithm?
- Computer
- Compiler for the programming language in which the algorithm will be implemented
- An operating system
What are the drawbacks of the measuring complexity in the experimental way?
The goal is to compute time complexity without____
We can compute complexity by analyzing an algorithm’s ______
Pseudocode
What are primitive/basic operations? What does it mean for something to be a constant in an algorithm?
How can we determine the complexity of an algorithm?
Why do we use asymptotic notation?
What is Asymptotic notation? How is it expressed? What do the variables mean?
Examples of computing the order of a function:
Another example of computing the order of a function:
Disproving an order of a function:
Use proof by contradiction
What are the primitive operations in this example?
What is the first/hardest method for computing the complexity of an algorithm?
What is the second method for computing complexity?
What is the easiest method of computing complexity?
What is the first rule for computing the order of a function?
What is the second rule for computing the order of a function?
Do the following examples for computing the order of a function:
