Introduction
What is Big O Notation?
Big O notation is used used as a tool to describe the growth rate of a function in terms of the number of instructions that need to be processed (time complexity) or the amount of memory required (space complexity).
This allows different algorithms to be compared in terms of their efficiency.
Note: Two algorithms can have the same Big O notation but in practice have wildly different execution times in practice. This is because the Big O describes the growth rate of complexity, not the actual complexity itself.
Time Complexity
Time complexity refers to the growth in the number of instructions executed (and therefore the time taken) as the length of the array to be searched increases.
Space Complexity
Space complexity refers to the growth in the size of memory space that is required as the length of the array is increased.
Algorithm Performance
There are a number of factors that affect the performance of search / sorting algorithms. Some algorithms perform well with high entropy (randomness) data, other algorithms work better when the data is partially sorted in some manner. This means that no one algorithm works best in every situation and the nature of the data being sorted needs to considered.
Bubble Sort
Bubble Sort
Time Complexity: O(n²) – Space Complexity: O(1)
Pretty much the worst sorting algorithm ever, mostly just used in teaching as a comparison tool. There are almost no legitimate use cases where it is the most efficient algorithm.
Insertion Sort
Insertion Sort
Time Complexity: O(n²) – Space Complexity: O(1)
Merge Sort
Merge Sort
Time Complexity: O(n log(n)) – Space Complexity: O(n)
Note: You are not required to know how to code a merge sort algorithm for your A-level exam, it is simply here for reference/comparison as it is a n log(n) algorithm, rather than a n² algorithm.
Linear Search
Linear Search
Time Complexity: O(n) – Space Complexity O(1)
Linear search is a simple searching algorithm that iterates through an array from left to right looking for a target item.
- If the target is found then it returns the index(location) of the item.
- If the target is not in the array then usually -1 is return (or None/Null depending on the implementation)
- If multiple instances of the target are found, the index of the leftmost instance is returned)
Linear search is generally considered to be quite inefficient, as the whole list sometimes has to be search, however it has an advantage over binary search in that it works on both sorted and unsorted arrays.
Binary Search
Binary Search
Time Complexity: O(log n) – Space Complexity O(1)
Binary search is a divide and conquer searching algorithm that can only be performed on a sorted list.
Each iteration through the algorithm the middle item of the array is checked to see if it is a match, it it is the index is returned, otherwise half the array is disregarded and the remaining component is searched in the same manner.
Binary search is highly efficient in its execution, however it’s application is limited to sorted arrays. This means that in most cases the list would have to be pre-sorted first. For arrays with static components that would work well but with arrays where the values change frequently any efficiency gains are lost due to the time taken to presort the data.