2.3 Algorithms Flashcards
Big-O notation
Used to express the time complexity or performance of an algorithm
O(1) (constant line)
An algorithm that takes constant time to execute
O(n) (linear line)
An algorithm that’s performance will grow in proportion to the size of the data
O(n²) (polynomial/quadratic time)
An algorithm whose performance is directly proportional to the square of the size of the data set
O(2n) (Exponential time)
An algorithm where the time taken doubles with every additional item added
O(log n) (Logarithmic time)
An algorithm that will grow very slowly as the size of the data set increases
Linear search
Where data items are searched one by one until the required one is found or the end of the list is reached
Binary search
The items must be sorted. Repeatedly divided the data list in half until there is only one data item left
Bubble sort
Comparing items in a list and swapping them into size order
Insertion sort
Sorts one data item at a time
Merge sort
Uses a divide and conquer approach.
The list is divided in half repeatedly until there are sublists of only 1 element. It is then merged together into larger sublists until it is recombined into a single sorted list
Quick sort
Dividing the sequence into to 2 sublists around an element called the pivot and organises all smaller values below and larger values above. This repeats until sorted
Dijkstra’s shortest path
An algorithm designed to find the shortest path between one particular start node and another in a weighted graph
A* algorithm
Follows Dijkstra’s algorithm but uses heuristics that biases the search toward the target
