Space and Time Complexity Flashcards
What are some ways to determine the efficiency of algorithms?
Their space and time complexity
Explain time complexity and when is an algorithm said to be efficient with respect to time.
Time complexity is how fast an algorithm executes all its instructions. When dealing with time complexity an algorithm is said to be efficient if it executes all its instructions within the minimum or shortest time possible.
What is space complexity and when is an algorithm said to be efficient in regards to space complexity?
Space complexity is the amount of RAM space or memory an algorithm uses to execute all its instructions. An algorithm is said to be efficient with regard to space complexity if said algorithm uses the least amount of possible RAM space or memory to execute all its instructions.
What are asymptotic notation and asymptotic analysis?
They are a method or way of analyzing the efficiency of algorithms, by analyzing the behavior of algorithms as their input increases or approaches infinity.
-> Asymptotic notation is a mathematical notation used for asymptotic analysis.
Explain the best, average, and worst-case scenarios of an algorithm.
-> Best Case: It is the minimum time an algorithm takes to execute all its instructions.
-> Average Case: It is the typical or average time an algorithm will take to execute all its instructions.
-> Worst Case: it is the maximum time an algorithm will take to execute all its instructions
State and explain the notations used to calculate the time complexity of algorithms.
-> Big O:
This is a mathematical notation used to calculate the
time it will take for an algorithm to execute as its
input increases, it calculates the worst-case scenario
an algorithm.
-> Omega:
It is a mathematical notation that measures the
the best-case time complexity of an algorithm.
-> Theta:
This mathematical notation calculates both the best
and worst-case time complexity of an algorithm.