# Big O Notation and Algorithm Analysis with JavaScript Examples

# Objectives

- Definition of Big O Notation
- Explain Simple Big O Expressions
- Explain Time Complexity

**WHAT IS BIG- O NOTATION**

Big O Notation helps us to evaluate which solution is best for us to accomplish to solve problems. If we have different solutions for a particular problem, It helps us to evaluate solutions as time wise and memory wise. It also gives us some idea how to approach solving the problem faster and using less memory.

Let’s say we have one problem and we have two different approaches to solve the problem. One approach a loop with adding some other operations in it and another has just some method (push or unshift etc.) in the function. How should we know which is the best approach to solve the problem based on Big O classifications. Here we can get advantage from Big O Notation classifications to get the best performance from our solutions. It is a system that compares the performance of the codes.

As the examples below ; There are 2 different implementations in JavaScript. They are all different approaches to solving the problems. It is not just using variables or loops and other operators. They are totally different approaches. How are we gonna know which solution is the best one?

**You cant use Big- O to compare the speed of two algorithms. Big- O only says how much slower an algorithm will get if you make double the number of items processed, or how much faster it will get if you cut the number half. (Ref:stack-overflow)**

**COMPARING 2 SOLUTIONS IN SAME PROBLEM**

We have to write a function that calculates the sum of all numbers from 1 up to some number **n**. We will compare those codes and try to see which one is the best approach to solving problems based on Big-O Notation. Our both codes are working well. But is this makes both of them efficient? Let’s take a closer look!

**1-Solution**

This is a regular function which has a for() loop with the counter. This code also gives us the same result. It’s totally working very well!

function addUpTo(n) {

let total = 0;

for (let i = 1; i <= n; i++) {

total += i}

return total;}console.log(addUpTo(3))

## 2- Solution

As you see this one is shorter than the first solution. This code also works very well and gives us the same result! But this is not the reason this code is more efficient. But It is different! There is no loop in the implementation.

function addUpTo(n){

return n * (n + 1) / 2;

}console.log(addUpTo(3))

**This is Demonstrations of solution with this formula code above**

**What makes the second solution better than the first one?**

Because it’s faster and it’s holding less memory space. Actually this is where we need Big-O Notation. It gives us direction to implement our code more efficient, faster and holding less memory space in our database! **Big o Notation does not care mainly about code readability. Readability is very important. But in our case here ; Big-O calculates how fast our code to execute as a performance wise and how much space it takes our memory space.**

**How to calculate timing performance in our solutions?**

We will build timing functions to evaluate our code performance! I will use performance.now() in the browser is going to give us the number of milliseconds since documents created time! I will implement this method to both solutions to see which code is executed faster than others!

**1-Solution**

function addUpTo(n) {

let total = 0;

for (let i = 1; i <= n; i++) {

total += i}

return total;}let t1 = performance.now();

addUpTo(1000000000)

let t2 = performance.now();

console.log(`Time Elapsed: ${(t2 - t1)/100} seconds.`)

As you see when I run the code 2 times there are two different numbers on my console. Even I did not add or changed any code after first execution. But We are having different out put.

**2-Solution**

function addUpTo(n){

return n * (n + 1) / 2;

}console.log(addUpTo(3))let t1 = performance.now();

addUpTo(1000000000)

let t2 = performance.now();

console.log(`Time Elapsed: ${(t2 - t1)/100} seconds.`)

As we see we are getting much less number than the first solution on the console. It’s almost under a seconds. Even though they have the same data but execution time is much faster ! It means our second solution is more efficient compared to the first one.

But calculation timing does not give us the perfect result to compare two solutions . Because we can get different results each time when we execute code as you see above from in same computer. Imagine if we do same calculations with different computer. We probably get different numbers. It is still good practice to compare both solutions like this but we can’t rely on these results.

**Big-O COMES TO GAME**

Since we calculated execution time with performance.now() method; it’s not really give us concrete proof that the second result is faster than the first one. So how are we gonna calculate it even if it’s not about timing?

Big-O notation counts number of simple operations has to perform. Because that remains constant no matter what computer you are using. It doesn’t change based on your computer model or speed. It’s so clear how many operations are used in your code. Time will determined always with numbers of operations. So it doesn’t matter if you are using an old computer or a brand new computer. Operations are constant. That is what Big O Notation care about !

**2- Solution**

We count our operation here as you see above . Our first operation is multiplication, another one is addition and we have division. Numbers (1)-(2) are not operations. The computer does not do too much work for the numbers if you compare to multiplication, addition and division. So we are clear about our operations now. It’s not really important what is the **n**. it can be(1) or it can be (1000000). **There are only 3 calculations which we should pay attention in this solution. It is not important what ever the value of (n). Our operations constant.**

**1-Solution**

We have a lot of operations here. We have addition counted as one operation But the difference is here;** We have a loop in this solution.** **So let’s say if the n(10) we have to add 10 things**. **It means 10 operations more**. **If it’s(1000000)** .**It’s mean (1000000) operations more**.** It’s not just one** **operation now**. **Operations number based on (n) in this solution. So whatever the value of the (n) it will also determine our operation numbers. When (n) groves operations also groves and its mean more assignments depends on the value of the (n). According to operations numbers , it’s also affect our code execution time performance and memory space. As you see above there are actually more operations than addition so it will all affect our code execution time and memory wise the way more than the second solution.**

As we also see demonstration of Counting operations, the second solution is still the winner. But Big-0 Notation classification with counting operators based on code execution. As performance gives us precisely which code is more efficient based on Big O notation classification !