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)

Image Source: geeksforgeeks.org

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)

Image Source: geeksforgeeks.org

The notation for binary search is O(log n).

Sorting Algorithms

Bubble Sort

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

Here’s the brief illustration explaning the working methodology of merge sorting algortihm: