2.3.1 Analysis, Design and Comparison of algorithms Flashcards
1
Q
What are the two things to check when developing an algorithm?
A
- Time complexity
- Space complexity
2
Q
What is time complexity?
A
- How much time is taken to solve a problem
- Big-O notation shows the effectiveness of the program
- Can be reduced by eliminating embedded loops when possible
3
Q
What does O(1) represent?
A
- Constant time complexity
- Time taken is independent drom number of elements inputed
4
Q
What does O(n) represent?
A
- Linear time complexity
- Time taken is directly proportional to number of elements inputed
5
Q
What does O(n^n) represent?
A
- Polynomial time complexity
- Time taken is directly proportional to the elements inputed to the power of n
6
Q
What does O(2^n) represent?
A
- Exponential time complexity
- Time taken will double with every additional item
7
Q
What does O(log n) represent?
A
- Logarithmic time complexity
- Time taken will increase at a smaller rate as the number of elements inputted increases
8
Q
What is space complexity?
A
- Amount of storage the algorithm takes
- Can be reduced by avoiding making copies
