2.3.1 Analysis, Design & Comparison of Algorithms Flashcards
State two pieces of information used to analyse an algorithm.
Time complexity
Space complexity
What is meant by time complexity?
How much time an algorithm requires to solve a particular problem
How is time complexity measured?
Using big-o notation
What does big-o notation show?
The time taken relative to the number of data elements given as an input
How can big-o notation be used?
To predict the amount of time taken to solve an algorithm given the number of elements stored
What is the name given to O(1)?
Constant time complexity
What is the name given to O(n)?
Linear time complexity
What is the name given to O(n²)?
Polynomial time complexity
What is the name given to O(nⁿ)?
Polynomial time complexity
What is the name given to O(2ⁿ)?
Exponential time complexity
What is the name given to O(log n)?
Logarithmic time complexity
What is the name given to O(n log n)?
Linearithmic time complexity
Describe what is meant by O(1).
The amount of time taken to complete an algorithm is independent from the number of elements inputted
Describe what is meant by O(n).
The amount of time taken to complete an algorithm is directly proportional to the number of elements inputted
Describe what is meant by O(n²).
The amount of time taken to complete an algorithm is directly proportional to the square of the elements inputted
Describe what is meant by O(nⁿ).
The amount of time taken to complete an algorithm is directly proportional to the elements inputted to the power of n
Describe what is meant by O(2ⁿ).
The amount of time taken to complete an algorithm will double with every additional item
Describe what is meant by O(log n).
The amount of time taken to complete an algorithm will half with every additional item
What is a logarithm?
An operation that determines how many times a certain (base) number is multiplied by itself to reach another number
What is meant by space complexity?
The amount of storage an algorithm takes
How can space complexity be reduced?
By performing all of the changes on the original pieces of data
How can time complexity be reduced?
By reducing the number of embedded loops where possible
What time complexity does a linear search algorithm have?
O(n)
What time complexity does a binary search algorithm have?
O(log n)
What time complexity does a bubble sort algorithm have?
O(n²)
