Big-O Notation
Big-O (O) is a mathematical symbol that points out the worst-case scenario of an algorithm in terms of time and input size. In the space of growth (input size) & time dimension, the Big-O chart illustrates the trade-off in using the searching and sorting algorithms.
But why is this important? Well, we already know that our coding is also subject to time growth and time dimension. Each time we optimize our code, we are either trying to minimize the memory usage or/and the compile times. Despite we want to achieve both of them at the same time, mostly, it will not be the case. Certainly, some we can create different algorithms that gathers the same result, but of course, with different performances.
So we got the point. The notation simply represents different algorithms’ performance. The algorithms are mainly divided into 2 categories: Searching and Sorting.
The chart below illustrates the time and input size relationship in different algorithms:
As can be observed above, finding out the best algorithm strictly depends on the input size.
Long story short, Big-O is used for comparing the worst case scenarios of different algorithms with respect to input size and time.
Upon looking up for some pretty visuals for explaining the algorithms, I have noticed geeksforgeeks.org has pretty nice explanations for each algorithm with implementations in different programming languages. I highly recommend you to check them out.
Linear Algorithms (Linear Search)
Linear search algorithm searchs for the target value in a target data set one by one, starting from its element.
For instance, if an item that you are searching for within a for loop is placed in the last slot, your algorithm will need to run for until the last element — which is the worst-case scenario for the case provided.
With the notation O(n), the n denotes the amount of data we need to filter. In the case of the given example, O(1) would be the best case scenario, which would meant that the element we were looking for was sitting as the first. And as explained above, the worst case scenario is O(n).
In brief, linear algorithms are denoted with O(n). The algorithms that are independent from the input size are called Constant Time algorithms and denoted by O(1).
Logaritmic Algorithms (Binary Search)
Binary search; which is also known as “half-interval search”, simply divides a given array into 2 pieces by comparing the target element with the middle element of the initial array. If the middle element is not equal to the target element, its value gets compared with the target value. If the target value is greater than the middle element of the array, the search continues with the upper half of the array — leaving out the lower half from the search. And vice versa if it’s lower than the middle element. Thus, Binary search is only functional with the sorted data set. With the exception of small arrays, binary search is faster than linear search.
The notation for binary search is O(log n).
Sorting Algorithms
Bubble Sort
As stated, some algorithms needs sorted data in order to be applied on — such as Binary Searching. The principle of bubble sorting is pretty simple: starting from the first element, it compares the value of it with all of the elements in the data set one by one. If it’s value is greater than the value of compared, the values are simply swapped within the data set. After finishing comparing the an element with the all of the remaining elements within the data set, the algorithm continues on by comparing the next element with the other elements one by one and this continues until the data set is finished.
For a quick example, you can check out the link below:
https://www.geeksforgeeks.org/bubble-sort/
Bubble sort algorithm is denoted by O(n²), which implies the usage of nested loops (for loop within a for loop).
Here’s an applied example of bubble sorting:
Merge Sorting
Merge sorting algorithm, simply cuts an array into half, creating a temporary new array to work on. This process continues until the arrays are divided into single elements. Once the data set with single elements is reached, algorithm starts to compare the elements with each other and build new temporary arrays with correct order.
Here’s the brief illustration explaning the working methodology of merge sorting algortihm:
