Skip to main content

Big O notation

[PLACEHOLDER]

 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

CRM - Overview Diagram

CRM is an interesting topic. I had the opportunity to work for a company where I participated in a project for the integration of: Microsoft Dynamics GP Microsoft Dynamics CRM Sharepoint (for the intranet)     I’ve also worked in the Digital Agency industry, involved in Web App solutions, where CRM strategies play an important role. For a client (Eg: An online company in retail selling shoes) would be beneficial to find a Shop (Digital Agency) that understands CRM from the strategic point of view and also offers services using software tools that facilitate the finding of insights, track consumer behaviors and helps to provide a personalize experience to the consumer; bringing value to the business. There are CRM solution providers out there that a Shop can partner with. To name a couple: Salesforce SDL There could also be a case where a Shop can create their own custom solution that could have as their center piece a BI system, created as a produc

Gaming trends: What to expect

Gaming continues with an accelerated evolution and significant business growth. The incredible virtual worlds are receiving thousands of real-time players, becoming another avenue for networking, as well as entertainment. This is just impossible to ignore. The gaming industry is one of the most dynamic and innovative sectors, constantly evolving and adapting to new technologies, consumer preferences, and market opportunities. Photo by Mikhail Nilov via Pexels   Newzoo forecast the game market will grow to $217.9 billion in 2023. Newzoo 2020 Global Game Market Cloud and gaming There was a time, not too long ago, when you would buy your games and play them by inserting them into your console or computer. As more gamers demand access to high-quality games on any device, anywhere, anytime, cloud gaming will become a mainstream option for delivering games over the internet. Games are now becoming available via subscription model. An example of this is the Microsoft Xbox game pass and Xbox L

Analytics and Attribution models

The customer journey is packed with multiple touchpoints, making it challenging to determine which of these “moments” (actions taken by the user) have played the most significant role in the conversion of the customer.  Photo by Mikael Blomkvist from Pexels Model attribution provides insights into how users interacts with your web and mobile apps. The decision-makers leverage the insights to understand what marketing efforts are driving “value”, allowing them to focus on the channels that provide the best Return on Investment (ROI).  There are several attribution models that can be used to assign credit. We will go through some of those in this article. Customer Journey - Beolle.com First touch attribution It is an awareness focus, being an introduction to the brand. This model gives the conversion credit to the first point of contact (i.e. a video or a social link).  Last touch attribution It is a model that gives the conversion credit entirely to the final touchpoint from which a lea

Your platform as a positive force in the world

If you are managing a platform, even if it is small, then you are leveraging one of the elements and popular channels used to build digital communities. These platforms, and channels, can come in the shape of websites, blogs, mobile apps, podcasts, vlogs, social media, or a combination of the ones mentioned. Photo by Tatiana Syrikova from Pexels   There are many reasons for building a community, such as sharing knowledge, promoting businesses, branding, the need for engaging with others, etc. However as Spiderman’s Uncle Ben said: “With great power comes great responsibility.” If you like to build better communities with more collaboration and less silos then how would you do it? How can communities come together to drive a “ positive force ”? The current world is mired in conflicts. How long are we willing to go on in such disarray? All the continents are in some kind of “a demonstration of partisanship, intolerance and selfishness”. There are nations in the Americas, Africa, Middl

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