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

AGILE For DIGITAL AGENCIES

Introduction Some Digital agencies have a project process where waterfalls still plays a big part of it, and as far as I can tell, the tech team is usually the one suffering as they are at the last part of the chain left with limited budget and time for execution. I do believe that adopting an Agile approach could make a Digital Agency better and faster. In this article I’m presenting you just another point of view of why it make sense looking at Agile Methodology.  Why Agile for a Digital Agency? The Agile movement started in the software development industry, but it has being proven to be useful in others as well. It becomes handy for the type of business that has changing priorities, changing requirements and flexible deliverables. In the Digital Agency of today you need a different mindset. Creative will always play a huge role (“the bread and butter”). But the “big guys” need to understand that without technology there is no Digital Agency. Technical resources are

AI with great power comes responsibility

Generative AI continues to be front and centre of all topics. Companies continue to make an effort for making sense of the technology, investing in their teams, as well as vendors/providers in order to “crack” those use cases that will give them the advantage in this competitive market, and while we are still in this phase of the “AI revolution” where things are still getting sorted.   Photo by Google DeepMind on Unsplash I bet that Uncle Ben’s advise could go beyond Peter Parker, as many of us can make use of that wisdom due to the many things that are currently happening. AI would not be the exception when using this iconic phrase from one of the best comics out there. Uncle Ben and Peter Parker - Spiderman A short list of products out there in the space of generated AI: Text to image Dall.E-2 Fotor Midjourney NightCafe Adobe Firefly

Upcoming updates to Gmail and Yahoo Mail in Feb 2024

Gmail and Yahoo Mail recipients can comprise over 65-70% of an organization's email target lists. Hence, organizations must ensure they prepare for the upcoming requirements for Gmail and Yahoo Mail for senders. Recently, Google and Yahoo jointly announced they will implement stricter controls to ensure their users receive relevant emails and can unsubscribe effectively.  Photo by Solen Feyissa on Unsplash   In this article, we summarize these upcoming Gmail and Yahoo Mail requirements and provide resources for additional readings if you choose to explore further. Key date: According to Adobe, Google and Yahoo Mail will implement these requirements in Feb 2024.   There are three (3) essential requirements 1. Authenticate your email sending domain We wrote a detailed article on the three pillars of Email Authentication in Essence of email deliverability - SPF, DKIM, DMARC and segmentation . In summary, Google and Yahoo will require the sender domain to have proper authentications,

Demystifying OKR Scoring

You have probably read that one of the many good things about OKRs is that it provides structure and clarity to work towards common goals. It helps connect company, teams and individuals’ objectives to measurable results.   Photo by Garreth Brown via Pexels In a previous Beolle article, Herak wrote about HOSKR and OKRs. In this iteration we will focus on the OKR scoring. Measuring the “How” The KRs in OKRs are the Key Results. With them we measure the progress towards the Objectives we have set. So how do we score them in a way that makes sense, and measure the success? Few “gotchas” before we start Grades are an indication where you're going. In OKRs, scoring between .6 to .7 is your target. Scores between .8 and 1.0 are rare, meaning they are not the usual. If you find yourself completing all your OKRs within this range then something is not correct, for example, your Objectives are not Ambitious enough, meaning you always knew you (or your company or your team) were going to ach

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