Notes: An Introduction to Scalability and Memory

# [An Introduction to Scalability and Memory](http://www.meetup.com/NY-JavaScript/events/231111946/)

[Javascript ES6 based](https://github.com/Haseeb-Qureshi/cs-fundamentals)

- Big O and asymptotic analysis
The number of CPU cycles? No, depends on the runtime. ENTER BIG 0!
Big O is about asymptotic analysis
How an algorithm scales
The rate of growth
How fast do the number s become unmanageble?
What happens when your input size is 10,000,000?
It's about scalability, not necessarily speed.
"The asymptotic rate of growth"
Principle of BIG O
n refers to the input size
  * O(n): y=x, y=Ax+b, linear
  * O(n^4): y=x^4+C
  * O(n*m): y=x+z+C
  * O(2^n + log(m)): considered exponential

Comprehension test
  * O(3n+5) -> O(n)
  * O(n+1/5n^2) -> O(n^2)
  * O(log(n)+5000) -> O(log(n))
  * O(2m^3+50+1/2n) -> O(m^3+n)
  * O(nlog(m)+2m^2+nm) -> O(nlog(m)+m^2+nm)


- Examples of different time complexities

Constant: O(1): math, pop, arr, and so on
Logarithmic: O(log(n)): binary search
Linear: O(n): linear search, iteration
Linearithmic: O(nlogn): sorting (merge, quick sort)
== efficient ========================================
Quadratic: O(n^2): nested looping, bubble sort
Cubic:  O(n^3)
Polynomial:  O(n^k): k can be 0.1 ~ more than 3. All "efficient" algotithms
Exponential: O(2^n): subsets, solving chess
Factorial: O(n!): permutations

- Time complexity analysis exercise
https://github.com/Haseeb-Qureshi/cs-fundamentals/blob/master/scalability-and-memory/timeComplexity.js
include, O(n)
isMiddleElement, O(1)
max, O(n)
substrings, O(n^2)  -> O(n^3) (slice costs O(n))
firstFive, O(1)
integerDivision, O(n/m)
hasVowel, O(n)
isSubstring, O(log(n))  -> O(n*m) // m: split, n: recursive
    // m dominants n    -> O(n^2)

y = nx + substr;
O(n^2)

(n-m)(n+m)
=n^2-m^2

- Scalability and bottlenecks
Bottleneck identification
Bigger Big O is the bottleneck

- Bottleneck identification exercise
For loop takes n
Sort takes nlogn
toLowerCase takes n
trim takes n

  1. check white space in the for loop
  2. do toLowerCase in the for loop (O(n) -> O(1))

  Actually the maximum number is 26, so O(1)

- Space complexity
  * max()
  * sbustrings()

- How memory is structured in a computer
  * Data Layers
  * CPU Registers
  * L1 Cache
  * L2 Cache
  * P RAM
  * V RAM

- Arrays and pointer arithmetic
- Pointer arithmetic exercise
- Cache-efficiency
- Cache-efficiency optimization exercise