Analysis of Algorithms Flashcards
1
Q
List the order of algorithm big O complexities from best to worst
A
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) <O(2n) < O(n!)
2
Q
For a binary search, what is the complexity?
A
O(log n), this is because the array is sorted
3
Q
For linear search, what is the complexity?
A
O(n), this is because we are searching through the entire array.
4
Q
What are the main criteria for comparing algorithms?
A
- Conceptual simplicity
- Difficulty to implement
- Difficulty to modify
- Running time
- Memory usage
5
Q
What is Space Complexity?
A
The amount of memory/storage required by an algorithm during its execution
6
Q
What is Time Complexity?
A
How much time an algorithm takes to execute based on the size of input?
