2.3.1 - Algorithms (Big-O) Flashcards
What is the purpose of Big-O
- Used to measure the efficiency/complexity of an algorithm.
- Can be used to measure the speed and/or memory requirements of an algorithm.
- N represents the number of items/elements.
Name and describe the complexity shown below
Logarithmic Complexity
Describes an algorithm whose growth rate decreases as the size of the data set increases, following a logarithmic curve. Scales well.
Example: Good for large data sets. A binary search where searching 200 values will just need one more iteration than if the data set only contained 100 values.
Name and describe the complexity shown below
Linear Complexity
Describes an algorithm where the execution time grows in direct proportion to the size of the data set it is processing
Example: Algorithms, which are based on a single loop to iterate through each value of the data set (Linear Search)
Name and describe the complexity shown below
Exponential Complexity
Describes an algorithm whose growth doubles with each addition to the data set. One item might take 1 second, two items would take two seconds, three items 4 seconds, and so on…
Example: Intractable Problems i.e. Travelling Salesperson
Name and describe the complexity shown below
Constant Complexity
Describes an algorithm that will always execute in the same execution time regardless of the size of the data set
Example: Returning the first item in an array, this remains the same regardless of the size of the array.
Name and describe the complexity shown below
Polynomial Complexity
Include quadratic algorithms O(N2), cubic algorithms O(N3) and so on… proportional to the polynomial of n
Example: Algorithms which are based onnested loopsare more likely to have a quadratic O(N2), or cubic O(N3) depending on the level of nesting used.
What are the possibles cases for the execution time of an algorithm.
The BEST CASE running time of an algorithm is the function defined by the minimum number of steps taken on any instance of size n.
The WORST CASE running time of an algorithm is the function defined by the maximum number of steps taken on any instance of size n.
The AVERAGE CASE running time of an algorithm is the function defined by an average number of steps taken on any instance of size n.
Give an example of the best and worst case for a bubble sort.
Best Case - The array is order in order, so just requires one pass through.
Worst Case - The array is in the total opposite order to the one required
What is the order of the complexities ranked from best to worst
BEST
Constant
Logarithmic
Linear
Polynomial
Exponential
WORST
Which algorithm/s has the following Big-O profile?
Linear Search
Which algorithm/s has the following Big-O profile?
Merge Sort
Which algorithm/s has the following Big-O profile?
Bubble and Insertion Sort
Which algorithm/s has the following Big-O profile?
Quick Sort
Which algorithm/s has the following Big-O profile?
Binary Search
