Chapter 3 Flashcards
What is the average case?
It is the average between the worst runtime case and the best runtime case which are both dependent on the type of data given to the algorithm
What is Big-O Notation?
Also called Order of magnitude, it is the dominant factor of runtime, the factor that grows the most. It helps describe the worst possible case for algorithm performance as size of the data increases
What is Brute Force?
It is a way of solving a problem in which every possible combination or solution is exhausted and its not fully optimised for the problem. It will often have a bad runtime performance.
What is matching off?
A technique where items are marked or “checked off” as they are processed or found, often used in searching and matching algorithms. This prevents processing the same item multiple times.
What is exponential?
An exponential algorithm is one which has a runtime of O(2^n). It grows very quickly
What is linear?
A linear algorithm is one which has a runtime of O(n). It grows proportionally to the size of the data
What is log linear?
A log linear algorithm has a runtime of O(n log(n)). Its faster than quadratic but slower than linear
What is logarithmic?
A logarithmic algorithm has a runtime of O(log n). Its input size is cut in half at each stage of the iteration. The time increases logarithmically with input size.
What is order of magnitude?
In algorithm analysis, it describes how the resource requirements grow relative to input size, ignoring constant factors.
What is quadratic?
A quadratic algorithm has a runtime of O(n^2). There are often nested loops involved in the algorithm.
What is time complexity?
Time complexity is the measure of how long it will take for an algorithm to execute. The number of steps involved. It takes the algorithms input size as the argument.
