Big O notation is the language we use for talking about how long an algorithm takes to run.

• We can measure in terms of efficiency what is good or bad code.

• We can measure what is code that can scale that as the number of Arrays or inputs increases.

What is a good code?

1- Readable

2- Scalable (Big O)

• Speed (Time complexity).
  • How fast is our function?
  • how much time that the function takes to run?
  • how many operation it will cost?

You want things to go faster, you might need to sacrifice more memory

• Memory (Space Complexity)
  • Computer has a limited memory

You want to use less memory, so you might need to increase the speed

Time complexity

Linear Time

BigO: O(n)

Performance: Fair. In the Big-O complexity chart it is considered Yellow color.

• Description: BigO(n)

Explanation: It takes linear time to find a nemo.

• The O(n) where BigO depends on n (number of items in the array).

                5               x
                4           x
Number of       3       x
Operations      2 
                1   2   3   4   5
                    Elements

Implementation:

    public void Linear(string[] arr){
        for(var i = 0; i < arr.Length; i++){
            if(arr[i] == "NEMO"){
                System.Console.WriteLine("Found NEMO!");
            }
        }
    }

Examples:

 var arr = ["nemo"];

Result: O(1)

 var arr = new string()[1000];

Result: O(1000)

Constant Time

BigO: O(1)

No matter how many times the array increase, we are always just grabbing the first item in the array. It's a flat line in terms of scalability.

Performance: Excellent. In the Big-O complexity chart it is considered Green color.

With 1 operation

                4               
                3           
Number of       2       
Operations      1   x   x   x
                0   1   2   3   4
                    Elements

function compressFirstBos(boxes){
    console.log(boxes[0]); //0(1)
}

With 2 operations

                4               
                3           
Number of       2   x   x   x   
Operations      1   
                0   1   2   3   4
                    Elements

function compressFirstBos(boxes){
    console.log(boxes[0]);  //0(1)
    console.log(boxes[1]);  //0(1)
}

Quadratic Time

BigO: O(n^2)

Every time we have a new element, the **number of operations increase dramatically **

Performance: Horrible. In the Big-O complexity chart it is considered Red color.

                9          x
                8         
                7          
                6         
                5        
                4              
                3       x    
Number of       2      
Operations      1   
                0   1   2   3   4 
                    Elements

An example is we want to log al pair of array

const boxes ['a', 'b', 'c', 'd', 'e']

function logAllPairOfArray(array){
   for(let i = 0; i < array.length; i++){
      for(let j = 0; j < array.length; j++){
        console.log(array[i], array[j]);
      }
   }
}
logAllPairOfArray(boxes);

Result:

a a
a b
a c
a d
a e
b a
...
e e

The Big O is O(n * n) or simply O(n^2)

Factorial Time

BigO: O(n!)

The most expensive one, we have a nested loop for every element that you are interacting.

Performance: Horrible. In the Big-O complexity chart it is considered Red color.

Space Complexity

Follow the code:

function myFunction(n){
   for(let i = 0; i < n.length; i++){
      console.log('hi!')
   }
}

myFunction([1,2,3,4,5]);

What is the space complexity of it?

Space complexity means additional space, so we do not really care how big the input, but when we call the function we reserve the space in memory. The Big in this case is: Big O = O(1)

Another example

function myFunction(n){
   let myArray = []; //Allocate space in Memory
   for(let i = 0; i < n.length; i++){. // i = 0 allocate space in memory
      myArray[i] = "hi"
   }
   return myArray;
}

myFunction([1,2,3,4,5]);

In this case we are adding one element per operation to the array. What is the complexity here? We create variables (i = 0)

We create data structure myArray

The big O for this case is: Big O = O(n)

Rules

Rule 1 - Always worst Case

What is the problem with this function?

const arr = ['dory', 'bruce', 'marlin', 'nemo', 'gill', bloat', 'nigel']

 function findNemo(array){
   for(let i = o; i < array.length; i++){
     if(array[i] === 'nemo'){
       console.log('Found NEMO!');
     }
   }
}
findNemo(arr);

Considering that NEMO is not at the beginning of the array, the first rule says that we already have to consider the worst so it means NEMO can be at the last index of the array. But the wrong on this function is that even tough the 'nemo' was found, the loop still proceed for the next until the very last index of the array.

An away to improve this code would be implement a break in the loop in order to stop the loop when nemo is found!

Rule 2 - Remove Constants

Considering the Big O of O(1 + n/2 + 100), we simple do not care about the numbers, because constants we cannot scale, we already know the number. However considering 'n' as a number that can contains an array of 1 element or 100000 elements and it is important and it means that this can be scaled, hence this is going to be measure as 'linear time complexity'

The result will be: O(n)

Other examples:

O(a + 50) the result will be O(a)

function compressBoxTwice(boxes){
   boxes.forEach(function(boxes) {
     console.log(boxes)
   }

   boxes.forEach(function(boxes) {
     console.log(boxes)
   }
}

this code is: O(2n) the result will be O(n)

Rule 3 - Different terms for inputs

When we have 2 or more parameters, such this example:

function compressBoxTwice(boxes, boxes2){
   boxes.forEach(function(boxes) {
     console.log(boxes)
   }

   boxes2.forEach(function(boxes) {
     console.log(boxes)
   }
}

The Big O of this code is: Big O(a + b). The reason that we should not use Big O(n) even tough there are 2 foreach, means that for this scenario, one input can have more items or less items comparing with the second input.

function compressBoxTwice(boxes, boxes2){
   boxes.forEach(function(boxes) {
      boxes2.forEach(function(boxes) {
     console.log(boxes)
     }
   }  
}

The Big O of this code is: Big O(a * b). When we have nested loop in multiple instead of sum the Big O.

Rule 4 - Drop Non-dominant terms

Considering the example bellow:

function printAllNumbersThenAllPairSums(numbers){
  numbers.forEach(function(number){
    console.log(number);
  });

  numbers.forEach(function(firstNumber){
    numbers.forEach(function(secondNumber){
    console.log(firstNumber + secondNumber);
    });
  });
}

The big O is 0(n + n^2). For this rule we drop the non dominant term, it means that we only keep the one that is more costs in terms of performance, in that case we care only in the most important term. So the result will be O(n^2) and we drop n because this is not important.

Other examples:

O(x^2+3x+1000+x/2) we simply by dropping non-dominant term when:

Considering x = 5
Then: x^2 (x * x) = 25
and 3x = 15
and 100 (constant)
and x/2 = 2.5

In this case 100 is the dominant term because represents the bigger number, however considering that we should drop the constant because we always have to be worried about scale and things intend to be large, so the dominant will be x^2 that is the second bigger number. Another example now comparing x = 500

Considering x = 500
Then: x^2 (x * x) = 250000
and 3x = 1500
and 100 (constant)
and x/2 = 250

In this case you can see that x^2 or x * x is equals 250000 and intend to be larger because it scales depending on the number of elements of the array.

Conclusion

------------------------------------------

References: https://www.bigocheatsheet.com/