Structured Algorithms Flashcards
(12 cards)
Explain
‘Big O’ complexity chart
A graph that shows the efficiency of algorithms by plotting the number of operations required to sort a given number of elements in the worst-case scenario (i.e. the target number is the last number to be found)
it shows how performance scales with input size
Explain
‘Big O’ notation
(time complexity)
A measure of how fast an algorithm runs based on the size of its input.
O(n) means algorithm speed grows at the same rate as its input size.
Recall
The two search algorithms.
LB
- Linear Search
- Binary Search
Explain
What occurs in the linear search algorithm?
An array is iterated through in index order until the target is found.
Explain
What occurs in the binary search algorithm?
halves sort
- If middle number > target number, reiterate for the lower half of the array (excluding the middle number)
- If middle number < target number, reiterate for the higher half of the array (excluding the middle number)
repeats and halves search area until target is found
note that binary search requires the array to be sorted.
Recall
The three sort algorithms.
BIS
- Bubble Sort
- Insertion Sort
- Selection Sort
Explain
What occurs in the bubble sort algorithm?
- i and i + 1 of an array are iterated over.
- if array[i] > array [i+1], swap them around.
Repeats in passes over the whole array until everything is swapped correctly.
Explain
What occurs in the insertion sort algorithm?
no clue bro
Explain
What occurs in the selection sort algorithm?
- Iterates and finds the maximum value of the list, and moves it to the end of the list, working backwards.
Repeats in passes over the whole array until everything is swapped correctly.
Recall
All sorting algorithms (that we’re required to know) have a time complexity of?
O(n²)
(this is not good, and gets geometrically slower as #elements increases)
Recall
What is the time complexity of the binary search algorithm?
O[log(n)]
(this is very good, but it requires the data to be sorted first.)
Recall
What is the time complexity of the linear search algorithm?
O(n) ☹️
this is okay but not ideal and gets slower with larger databases
