Big O notation is a mathematical notation used for describing the limiting behaviour of a function.
As a developer (programmer), you could use Big O to understand the performance of an algorithm. By using this concept a developer can evaluate a function’s run-time based on the input(s) passed.
A developer can also use it to compare algorithms' efficiency within the same domain. This comparison can well be for evaluating the performance. The algorithm that yields the lower Big O value is identified as the optimal one.
 |
Photo by Anni Roenkae from Pexels
|
What is the "O" in Big O? “The letter O is used because the growth rate of a function is also referred to as the order of the function” - wikipedia (https://en.wikipedia.org/wiki/Big_O_notation).
In the list below you can see the various functions:
| Notation | Name |
|---|---|
| O ( 1 ) | Constant |
| O ( log log n ) | Double logarithmic |
| O ( log n ) | Logarithmic |
| O (( log n ) ^c ) | Polylogarithmic |
| O ( n ) | Linear |
| O ( n log ∗ n ) | n log-star n |
| O ( n log n ) = O ( log n ! ) | Linearithmic, Loglinear, Quasilinear, or "n log n" |
| O ( n ^2 ) | Quadratic |
| O ( n ^c ) | Polynomial or Algebraic |
| O ( c ^n ) | Exponential |
| O ( n ! ) | Factorial |
Let us go through four (4) of the functions from the table above. This is to simplify the explanation of the concept, as well as to showcase why the Big O is useful for developers when creating, refactoring, reviewing algorithms.
O (1)
The constant time is relative to the input is a good place to be when working on your algorithms. function ArrayConsoleWrite(x){
let arrayOfX = [11,12,13,14]
console.log(arrayOfX[x])
return arrayOfX[x]
}
O (n)
In the linear function, time of execution will grow as “n” grows (meaning as many steps it needs to take).
function DummyWhileLoop(){
const varx = [11,12,13,14] // length is 4
let x = 2 // valid values are from 0 to 3, which are the positions of the array
while (x < varx.length) {
console.log(varx[x])
x++
}
}
In this example the closer x is to the length of the array the faster it will resolve. The worst case will be if every single item of the array requires to get printed.
O (n^2)
In the case of the quadratic function, time grows exponentially. You can see this type of issue in algorithms that have nesting loops, as an example.
Another type of problem that can be evaluated with the quadratic function is in the Shortest Path algorithm for solving a maze, in particular if the Dijkstra's Algorithm is applied.
 |
| Photo by Mitchell Luo on Unsplash |
O (n!)
The factorial function is the one you want to avoid, as it is the indicator of worst performance. The algorithm will go through the permutation, meaning all the possible combinations/paths.
For occasions where this path cannot be avoided the distributed computing will come to the rescue. Cloud services can become handy to help out in order to scale accordingly, providing the power needed.
An example would be the algorithm for the TSP (Travel Salesman Problem) when solving it by using brute-force search.
 |
| TSP problem |
In summary
Big O is commonly used in worst case analysis. This means to describe the worst case running time of an algorithm. In contrast, Big Omega is used to describe the best case running time.
