2.3.1 - Analysis, Design and Comparison of Algorithms Flashcards
What are the two features that must be considered when designing an algorithm?
Time complexity and space complexity.
What is time complexity?
How much time it takes to solve a particular problem.
What is space complexity?
The amount of storage the algorithm takes up.
What is Big-O notation?
A way of representing the time complexity of an algorithm.
What are the five types of Big-O notation?
Constant
Linear
Polynomial
Exponential
Logarithmic
How is a constant time complexity written in Big-O notation?
O(1).
How is a linear time complexity represented in Big-O notation?
O(n).
How is a polynomial time complexity written in Big-O notation?
O(nn).
How is exponential time complexity written in Big-O notation?
O(2n)
How is logarithmic time complexity represented in Big-O notation?
O (log n).
What does a constant time complexity mean?
The amount of time taken to complete an algorithm is independent of the number of elements inputted.
What does a linear time complexity mean?
The amount of time taken to complete an algorithm is directly proportional to the number of elements inputted.
What does polynomial time complexity mean?
The amount of time taken to complete an algorithm is directly proportional to the elements inputted to the power of n.
What does exponential time complexity mean?
The amount of time taken to complete an algorithm will double with every additional item.
What is logarithmic time complexity?
The time taken to complete an algorithm will increase at a smaller rate as the number of elements inputted.
