Introduction

This digests series originates from ThePrimeagen's "The last algorithms course you'll ever need" 👍.

1. Rationale
2. Big O notation
3. Remarks

• Though there is a point where algorithms become useless for the average developer, numerous algorithms are super useful.
• Developers use some of those algorithms all the time without even noticing it.
• In job interviews, data structures and algorithms are like a secret handshake to get into a very good paying job.
• As a result, it's best to learn the handshake.

• Big O is a convention used to classify algorithms requirements according to 2 criterias : time and memory.

• It is not a measurement system (since it involves no units) but a way to assess the efficiency of an algorithm.

• It helps choosing specific data structures / algorithms to use when implementing a more complex algorithm with a general purpose.

• The Big O notation describes the growth of an algorithm's consumption of time or memory with respect to the growth of its input.

• Growth of time or memory consumption can be represented by a function of the size of the input i :

  growth type	mathematical function	Big O notation
  Constant	f(i) = A	O(1)
  Logarithmic	f(i) = A * log2(i) + B	O(log n)
  Linear	f(i) = A * i + B	O(n)
  Quadratic	f(i) = A * (i ** 2) + B	O(n²)
  Cubic	f(i) = A * (i ** 3) + B	O(n³)
  Exponential	f(i) = (A ** i) + B	O(2ⁿ)

Note : A and B are constants.

• Example of a linear function :

const linear = (i:string):void => {
    // first iteration, time consumption grows linearly with input
    i.split(``).forEach((c:string):void => { console.log(`one: ${ c }`); });
    // second iteration, time consumption grows linearly with input
    i.split(``).forEach((c:string):void => { console.log(`two: ${ c }`); });
    // no iteration, time consumption is constant
    console.log(`The Big O notation for this function is 2 * O(n)`);
};

• Constants affect the growth marginally, so they can safely be dropped out of Big O notation.
• The notation always consider the worst case scenario for an algorithm :
  • For instance, any conditional halting of execution is to be ignored.
• The purpose of Big O notation is to assess an algorithm's theoretical efficiency as opposed to its practical efficiency :
  • For instance, algorithms with a high complexity may perform better than less complex ones provided the input is small enough.