• Complexity and Big O notation

• O(1) — Constant Time
  Given an input of size n, it only takes a single step for the algorithm to accomplish the task.
• O(log n) — Logarithmic time
  Given an input of size n, the number of steps it takes to accomplish the task are decreased by some factor with each step.
• O(n) — Linear Time
  Given an input of size n, the number of of steps required is directly related (1 to 1)
• O(n²) — Quadratic Time
  Given an input of size n, the number of steps it takes to accomplish a task is square of n.
• O(C^n) — Exponential Time
  Given an input of size n, the number of steps it takes to accomplish a task is a constant to the n power (pretty large number).

let n = 16;
O (1) = 1 step "(awesome!)"
O (log n) = 4 steps  "(awesome!)" -- assumed base 2
O (n) = 16 steps "(pretty good!)"
O(n^2) = 256 steps "(uhh..we can work with this?)"
O(2^n) = 65,536 steps "(...)"

function isFriend(name){ //similar to knowing the index in an Array 
  return friends[name]; 
};
isFriend('Mark') // returns True and only took one step
function add(num1,num2){ // I have two numbers, takes one step to return the value
 return num1 + num2
}

//You decrease the amount of work you have to do with each step
function thisOld(num, array){
  var midPoint = Math.floor( array.length /2 );
  if( array[midPoint] === num) return true;
  if( array[midPoint] < num ) --> only look at second half of the array
  if( array[midpoint] > num ) --> only look at first half of the array
  //recursively repeat until you arrive at your solution

}
thisOld(29, sortedAges)

//The number of steps you take is directly correlated to the your input size
function addAges(array){
  var sum = 0;
  for (let i=0 ; i < array.length; i++){  //has to go through each value
    sum += array[i]
  }
 return sum;
}

//The number of steps you take is your input size squared
function addedAges(array){
  var addedAge = [];
    for (let i=0 ; i < array.length; i++){ //has to go through each value
      for(let j=i+1 ; j < array.length ; j++){ //and go through them again
        addedAge.push(array[i] + array[j]);
      }
    }
  return addedAge;
}
addedAges(sortedAges);
//Nested for loops. If one for loop is linear time (n)
//Then two nested for loops are (n * n) or (n^2) Quadratic!

//The number of steps it takes to accomplish a task is a constant to the n power
//Thought example: Trying to find every combination of letters for a password of length n

• Generators

• asyncio package
• Advanced

We will have to take into account the next three elements:

• External request from an external client (an HTTP request from a browser, etc).
• Your code running in some container (a Django app running on mod_wsgi, a Python script listening to RabbitMQ, etc).
• Pieces of infrastructure (MySQL, Redis, RabbitMQ, etc).

Two types of scaling:

• Vertical: You scale by adding more power (CPU, RAM) to your existing machine.
• Horizontal: You scale by adding more machines into your pool of resources.

A load balancer (software or hardware) is placed just after the request arrives to our servers. It chooses between workers which one will process the request.

• HAProxy
• NGINX
• Traefik

Precalculate results, pre-generate expensive indexes, and storing copies of frequently accessed data in a faster backend.

There are two types of cache:

• Application caching requires explicit integration in the application code itself. Usually it will check if a value is in the cache; if not, retrieve the value from the database; then write that value into the cache.
• Database caching, when you configure the database cache.

In-memory cache are software that stores the cache content on RAM (Redis, Memcache).

Another kind of cache which comes into play for sites serving large amounts of static media is the content distribution network (CDN). They can also provide geographic distribution.

Cache invalidation is the procedure to avoid inconsistencies between the updated data and the data stored into the cache.

• Memcache
• Varnish
• Cassandra
• Redis

The dispatcher multicast the request to all workers of the pool. Each worker will compute a local result and send it back to the dispatcher, who will consolidate them into a single response and then send back to the client. This pattern is used in Search engines like Yahoo, Google to handle user's keyword search request … etc.

Message queues allow your web applications to quickly publish messages to the queue, and have other consumers processes perform the processing outside the scope and timeline of the client request.

They allow you to create a separate machine pool for performing off-line processing rather than burdening your web application servers.

• RabbitMQ

• Fallacies of distributed computing