Big O

Overview

Big O help us find out how well the problem is solved.

We use it to distinguish that code from good code, good code from great code.

->great developer

What is good code?

1. Readable

2. Scalable

Big O allow us to measure the idea of scalable code.

How can we make sure that there is a way for us to measure in terms of efficiency, what is good code, 

what is bad code, and what is code that can scale that as the number of arrays or inputs increases, 

it doesn't constantly slow down more and more.

We can compare it to different algorithms or in this case, function using big O and say which one is better than the other when it comes to scale. Regardless of our computer differences.

When we talk about Big O and scalability of code, we simply mean when we grow bigger and bigger with inputs, how much does the algorithm or functions slow down.

When the Elements increase, the number of operations increased over and over. Some increase much, some doesn't increase much.

Instead of using performance and using time to measure the efficiency of our function, we can just calculate how many operations a computer has to perform because each operation takes time on a computer.

O(n)

The picture describes that 4 item in an array.

We do the asking loop "is it the nemo ?" 4 times 4 operations

As the items increased, the operation increased.

This is linear. We can say this findNemo notation O(n).

As the item increased, we find the time scaled.

O(1)

This is O(1), what we called constant time.

It is how many items in boxes, we just grasping the first item in the array.

The number of operations just stay flat.

function funChallenge(input) {

  let a = 10; //O(1)

  a = 50 + 3; //O(1)

  for (let i = 0; i < input.length; i++) {

    anotherFunction(); //O(n)

    let stranger = true; //O(n)

    a++; //O(n)

  }

  return a; //O(1)

}

We can calculate the function which is BIG O(3+3n).

It can be simplify as O(n).

function anotherFunChallenge(input) {

  let a = 5;//O(1)

  let b = 10;//O(1)

  let c = 50;//O(1)

  for (let i = 0; i < input; i++) {

    let x = i + 1; //O(n)

    let y = i + 2; //O(n)

    let z = i + 3; //O(n)

  }

  for (let j = 0; j < input; j++) {

    let p = j * 2; //O(n)

    let q = j * 2; //O(n)

  }

  let whoAmI = "I don't know";//O(1)

}

BIG O(4+5n).-> O(n)

How to simplify? 4 rules

Rule 1: Worst Case

If the worst case happen, we just need to run all the case of it.

However, we can add break when the function find the target.

The effort time will decrease.

We can know that in the following situation.

It may be O(1), O(4) for us to find the nemo.

The worst situation is O(n).

Rule 2: Remove Constants

O(n+1), O(n+10000) -> O(n)

Because we consider the scale, we omit the constants.

On the other example,

We don't really care about how steep the line is.

O(2n), O(n/1000) -> O(n)

We care about how the line moves as our inputs increase.

Rule 3: Different terms for inputs

When the function has two different arrays of inputs,

we say O of A plus B.

When the loops were actually nested and they are not one after another,

the big O is A times B.

Rule 4: Drop Non Dominants

if we call the function > printAllNumbersThenAllPairSums([1,2,3,4,5]),

the Big O will be O(n+n^2).

The n will be drop due to the insignificance in the function.

Hence, it the Big O should be O(n^2). It is quadratic.