Define
‘Big O’ notation
A notation that measures the efficiency of algorithms by notating the relationship between the number of operations (O) and number of elements in a set (n).
List
Types of search algorithms
- Linear Search
- Binary Search
Recall
The time complexity of a linear search.
O(n).
Recall
Steps of a Linear Search
Iterate over a set at a linear rate until the target is found.
Recall
The time complexity of a binary search.
O[log(n)].
Recall
Steps of a binary search
- Compare the middle element of the set to the target.
- If it’s greater than the target, repeat iteration on the lower half of the array, and vice versa if it’s less than the target.
- Repeat until found.
(The set MUST BE SORTED.)
List
Types of Sorting Algorithms
- Bubble Sort
- Insertion Sort
- Selection Sort
(BIS)
Recall
The time complexity for every sorting algorithm covered.
O(n^2)
Which sorting algorithm has a time complexity of O[n * log(n)]?
(Extension)
quicksort.
List
The steps of a bubble sort.
- Iterate through an array (
arr)), comparing each value (arr[i]) by its succeeding value (arr[i+1]) and swapping themif arr[i] > arr[i+1]. - Repeat this until no swaps are done, indicating completion.
List
The steps of a selection sort.
Instantiate a ‘sorted’ and ‘unsorted’ set, storing the ‘unsorted’ data in the ‘unsorted’ set, and leaving the ‘sorted’ array empty.
- Iterate over the ‘unsorted’ set, popping the smallest number, and adding it to the ‘sorted’ set.
(‘pop’ — fetch value and then remove from set)
List
The steps of an insertion sort.
Instantiate a ‘sorted’ and ‘unsorted’ set, storing the ‘unsorted’ data in the ‘unsorted’ set, and leaving the ‘sorted’ array empty.
- Iterate over ‘unsorted’ set linearly, popping its value, and adding it to the ‘sorted’ array.
- In the ‘sorted’ set, the value’s index is shifted down until it finds a number less than it.
- Repeat until ‘unsorted’ is empty.
(like a selection sort-bubble sort hybrid)
