Blog / Data Structures & Algorithms
Introduction to Big O
  • Nov 15, 2020
  • 66
  • 92

Big O is one of the most important topics for any software developer or engineer. No matter what company you are working, where you live, or how long it will be from now, this concept will be around and it is what makes you a better developer. Big companies, like  F.A.A.N.G., all know this which is why you won't get any of their interviews without encountering this topic. 


Advertisement
 


1. What is Big O

Big O, the official term is Big O asymptomatic analysis, can help us to see how well a problem is solved. Any coder, who is given enough time, can solve a problem. However, what matters is how well the problem is solved. We will talk about what Big O is, how we define it and then how to use Big O and it's different notation to distinguish bad code from good code, or good code from better code.

2. What is Good Code?

Good code is defined by two criteria: Readability and Scalability. Readability determines if your code is just generally clean, and if others can understand your code. Scalability is the ability to adapt of your code. Big O is what allows us to measure this idea of scalable code. 

3. Big O and Scalability

Consider a cake baking procedure as an example of scalability. Let's say, we have a task to bake a cake with provided recipe and a kitchen. There are many way to bake a cake which will result in either a good or a bad product. It all depends on how well we utilize the kitchen to work well with the provided recipe. We can say, our baking procedure must adapt to the provided resources that we have, in other words, it must scalable with the available resources.

Well, computers are machine which need to work in order to produce something for human. Computers work the same way as the kitchen in the example above. We have instructions that we give it through code and these code are running by computers to produce some sort of an output. A coder is  someone who gives the code as instruction to a computer, just like how to use recipe to bake a cake, there are many ways to code and solve problem which will result in either good or bad outcome. So, your code performance must scalable to the provided machine which executes it. Big O notation is used to measure how well your code performs in any computer.



So, how is Big O used to measure your code performance? Consider below piece of JavaScript code. We are writing a simple function to catch Pikachu!

const pokemon = ['Pikachu', 'Meowth', 'Bulbasaur'];
 
function catchPikachu (array) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === 'Pikachu') {
       console.log('Catch Pikachu!');
    }
  }
}
 
catchPikachu(pokemon);

The above code would run really fast in modern computers because, well, computers are fast now! The other factor that make it really fast is the list of input array is small. We only have 3 items in our pokemon array. Let's try it again with another array of more Pokemon and have a little trick to calculate how long your code take to execute in my machine.

const pokemon = ['Pikachu', 'Meowth', 'Bulbasaur'];
const morePokemon = ['Pikachu', 'Meowth', 'Bulbasaur',  'Charmander', 'Squirtle', 'Caterpie', 'Weedle', 'Pidgey', 'Rattata', 'Spearow'];
const manyPokemon = new Array(1000000).fill('Pikachu');
  
function catchPikachu (array) {
  let t0 = performance.now();
  for (let i = 0; i < array.length; i++) {
    if (array[i] === 'Pikachu') {
       console.log('Catch Pikachu!');
    }
  }
  let t1 = performance.now();
  console.log('Call to catch Pikachu took ' + (t1 - t0) + ' milliseconds');
}
  
catchPikachu(pokemon); //took roughly 0 millisecond
catchPikachu(morePokemon); //took roughly 0.1 millisecond
catchPikachu(manyPokemon); //took roughly 7 millisecond

Well, we can see different outcomes depend on the size of the input, and, of course, the machine we use to execute the code. One of the reason you may have different results of how long your code took than mine is because you ran your code in your computer and I ran mine in my computer. 

Big O notation is the language which is used for talking about how long an algorithm takes to run. We can compare two different algorithms using Big 0 to say which one is better than the other in term of scale regardless of our computer and input differences. 

So, we have been introduced to Big O and have an idea of the use of it. We will discuss how Big O is calculated and which Big O number represent horrible and excellent code performance in the next posts.

Read more in this series:


Using cherry-pick to select specific commits for your Pull Request.1. Create a new branch based on the target of the Pull Requestgit branch cherry-branch origin/master2. Switch to a new branchgit chec ...

After deployment Angular and API on IIS, it's working fine unless I refresh the page. Once refreshed, the web encountered 404 error. In this article, I will explain how to resolve this.Since Angular i ...

There are some benefits of keeping both UI and API parts in the same place for small projects. In this article, I will explain how I did to deploy Angular Web and ASP .Net Core API in the same folder ...

I got CORS error after publishing my API and Angular app to IIS even though CORS is enabled and the origins of the Angular app is added. Below is how I resolved this issue.Just simple, make sure you s ...

In Object-Oriented Programming, S.O.L.I.D refers to the first five design principle for the purpose of making software designs more understandable, flexible, and maintainable. The principles was first ...

1. The Situation:Error Message:&nbsp;Pulse Secure Application failed to load Java. Please install correct JRE version.Description: This issue happens when I'm using a M1 Mac with a correct version of ...

Accelerated Mobile Pages (AMP)&nbsp;focuses on delivering static content from publishers as quickly as possible and possibly rewards early adopters with a boost in rank. Let's see how to implement it ...

Below is how to decrypt/convert a Hex string value into text using VB.Net:Decrypting Hex string value to string in VB.Net Function HexToString(ByVal hex As String) As String Dim text As New Sy ...

After a month of publishing on Google Play, Jungle Words has made it to the Top Android Games To Try Out In April 2021. Please check it out!&nbsp;GameKeys.netGameKeys is a website which introduces gam ...