Skip to main content

Big O notation

 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

Note: For a more detailed explanation of the Shorter Path algorithm go to the links in our reference section at the end of this article.

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.

 


References

Trending posts

Adobe Summit 2022 - Experience Platform

 Our hero image features many air balloons flying, scattered in a blue sky. Each of them has characteristics in their designs that are “part of a whole”, which in this case is an exhibition that is part of a festival. Now, let us leverage this analogy, mapping it to the elements that are relevant for this post’s agenda. Think about the pieces of data scattered through different systems, which combined (behaviour and PII data) becomes part of a whole: an enriched consumer profile that can provide you a “360 view”. This allows corporations to find opportunities, and turn them into value: “enabling ways to engage with that customer(s) to meet a cluster of business goals.” Photo by Lad Fury from Pexels   The objectives for this article are: To provide our takeaways from two (2) Adobe summit 2022 sessions, related to the Adobe Experience Platform and Real-time CDP (Customer Data Platform). Those sessions being S401 (AEP a modern foundation - by Klaasjan Tukler) and  S408 (DMP vs CDP:

Quality Assurance for mobile applications

By: Herak Quality Assurance is an important aspect of Software Development Cycle and it has become even more important with the advent of mobile applications. This is because mobile applications are typically more complex and needs to be supported across a plethora of platforms. Often the same application needs to be coded in different programming languages to support different platforms for example Objective C for iOS and Java for Android. This results in multiple code base and requires multiple streams of testing. QA also need to pay special attention to ensure that the user experience of the app remains somewhat similar across the multiple environments. Thus traditional QA practices need to evolve to adapt to the needs of the mobile app testing. In this article I am going to discuss the first two phases of QA, Preparatory Phase and Testing Phase. I will discuss how QA needs to adapt to the testing need of mobile applications and include links to resources which will help

Research around JIRA vs TFS

By: Carlos G.    An opportunity came from a colleague to discuss the case of company “X” for improving the ALM by introducing tools to this company. The challenge was to decide between Microsoft and Attlasian . He came to me because I’m a Microsoft kind of guy and he wanted the opinion from my perspective, not as a consultant, but as a friend of what he was trying to accomplish. He said that even though I was inclined to a technology I was able to explore other things and be “fair”. I agreed to be a part of his research because of 3 things: because of my curiosity I'm always willing to learn new techy stuff. Sometimes is good to be the dumbest one of the group. You learn so much! This was a story that I could blog about. (Of course no names are used in this post). My first impression was thinking “cool”; let’s compare Visual Studio TFS vs JIRA. Immediately I got a comment back with: “ Sure but JIRA by itself is more like an issue tracker in simple terms ”. That sa

AWS Amplify as low-code for infrastructure

Low-code development platforms are dominating many conversations lately. Many believe that low-code development platforms will account for millions of USD in revenue in the next five (5) years. An article by Forbes highlights that “ it will account for more than 65% of application development activity by 2024 ”. Some believe it will be the answer to all their development needs. Photo by Tima Miroshnichenko from Pexels  But low-code is not a new concept. The difference now is that its audience has amplified. For developers (or even advanced users) who have been in the Microsoft  ecosystem for a while have already experienced the assembly of software solutions with little effort using tools such as Microsoft Excel, Access, Visual Studio (assembling forms) and others. Putting Microsoft aside, and prior to this “low-code revolution” which has reached high altitude in the last couple of years, there have been many online veterans which allow a user to assemble simple to medium complex

This blog uses cookies to improve your browsing experience. Simple analytics might be in place for pageviews purposes. They are harmless and never personally identify you.

Agreed