“Understanding Big O Notation”
Optimization is key when trying to improve performance of your software.
When it comes to Big O, it’s only important when you’re dealing with Big Data in the hundreds of thousands if not millions.
Let's start by displaying popular options for Big O Notation and their order of performance.
The List below is ordered from Most Performant to Least Performant:
- Binary Search — O(Log N)
- Linear Search — O(N)
- Merge Sort — O(N Log N)
- Bubble Sort — O(N²)
Let us look at Linear Search first as it is the easiest to understand.
Linear Search O(N)
For this example we are going to use the follow array and target to display this concept:
int[] _sortedArray = { 2, 4, 5, 6, 7, 8, 10, 12, 14, 15 };
int target = 10;
With Linear Search algorithm you are essentially looking through each element in a list to find your target. I have an array of integers with 10 elements and within that array I am looking for the target 10. Then I will iterate through each element until I find it.
In the best case scenario I can find it on my first try which would correlate to O(1). In the worst case scenario I can find it on the last try which in this case would correlate to O(10). But in this example it would turn out to be O(7).
Let us take a look at a code example using C# and Unity.
If we input our example array and target we get the following output:
Binary Search O(Log N)
For this example we are going to use the follow array and target to display this concept:
int[] _sortedArray = { 2, 4, 5, 6, 7, 8, 10, 12, 14, 15 };
int target = 10;
Binary Search also known as logarithmic search is a search method that locates a target value within a sorted array. The binary search compares the target value to the array’s middle element. Take note that this method only works with sorted arrays unlike the linear search method.
In simpler terms binary search takes a divide and conquer approach. Essentially we take the length of the array and divide by two. Then we ask the question, does the middle element match the target? If not we then ask is the target value greater than the middle element? If so we use the right side, if not we use the left. Then we repeat the series of questions until we are able to answer the question of if the target matches the middle element.
Take a look at this example below using C# and Unity.
If we input our example array and target we get the following output:
Using the same array from our Linear Search example we can see that Binary Search is 3 counts faster than Linear search! But what if we have an array that is not sorted? Well then before we can apply Binary Search we must sort the array. Continue reading to learn how…
Bubble Sort O(N²)
Bubble sort, also known as sinking sort, is a basic sorting algorithm that passes over the list repeatedly, compares nearby entries, and swaps them if they are out of order. The process of traversing the list is continued until the list is sorted.
This basic method performs badly in practice and is mostly used as an instructional tool. Quicksort, timsort, and merge sort are more efficient algorithms.
Take a look at this example below using C# and Unity.
While Bubble Sort is not very good practice it is good for displaying the concept of sorting algorithms. In practice merge sort (shown below) is much better and more performant as bubble sort as a massive time complexity.
Merge Sort O(N Log N)
The Merge Sort algorithm is a Divide and Conquer algorithm. It divides the input array in half, calls itself for each half, and then combines the two sorted parts.
Take a look at this example below using C# and Unity.
