path: root/notes.md

* Efficient procedures for solving large scale problems. Scalability.
* Scalability
* Classic data structures
* Algorithmic Thinking
* Sorting & trees


A data structure is a way to store and organize data in order to facilitate
access and modifications. No single data structure works well for all purposes,
and so it is important to know the strengths and limitations of several of them.

Hard problems: There are some problems, however, for which no efficient solution
is known. These are known as NP-complete problems.

NP-complete problems are interesting because an efficient algorithm hasn't been
found and nobody has proven that an efficient algorithm cannot exist.

Np-complete is like god. Nobody knows if an efficient solutions exists or not.

Also, if an efficient algorithm can be found for one NP-complete problem then an
efficient algorithm must exist for all of them.

If you can show that a problem is NP-complete, you can instead spend your time
developing an efficient algorithm that gives a good, but not the best possible,
solution.

The "traveling-salesman problem" is an NP-complete problem. So any solution is
good enough because an efficient solution has not been found yet.

In order to elicit the best performance from multicore computers, we need to
design algorithms with parallelism in mind. Multithreaded algorithms exist to
take advantage of multiple cores. Championship chess programs use this.


1.1-1: Give a real-world example that requires sorting or a real-world example that
requires computing a convex hull.

    Names in an address book.

1.1-2: Other than speed, what other measures of efficiency might one use in a
real-world setting?

    The amount of space required.

1.1-3: Select a data structure that you have seen previously, and discuss its strengths and limitations.

    Balanced binary search trees are excellent for finding data quickly but a
    bit complicated when it comes to trying to keep it balanced efficiently.

1.1-4: How are the shortest-path and traveling-salesman problems given above similar? How are they different?

    The shortest path problem is looking for an efficient solution that routes
    from point A to point B. The traveling-salesman problem is similar except
    that the sales person needs to visit multiple locations then return to the
    starting point in the most efficient way. These problems are similar because
    the shortest path from point A to B can be used to help determine a good
    enough solution for the traveling-salesman problem.

    Both of these problems are considered an NP-complete problems because it
    hasn't been proven if an efficient algorithm can or cannot exist.

1.1-5: Come up with a real-world problem in which only the best solution will do.
  Then come up with one in which a solution that is "approximately" the best is good enough.

    * Traveling to Mars. Humans have a finite amount of time to live so choosing
      a point in time to travel that doesn't align with orbital conditions might
      make it impossible for humans to survie the trip.
    * Driving directions from point A to B.

# Efficiency

Different algorithms devised to solve the same problem often differ dramatically
in their efficiency.

* insertion sort takes n time to sort n items.
* merge sort takes time roughly equal to nlg(n) time to sort n items.

By using an algorithm whose running time grows more slowly, even with a poor
compiler, computer B runes more than 17 times faster than computer A!

As the problem size increases, so does the relative advantage of merge sort.


1.2-1: Give an example of an application that requires algorithmic content at
the application level, and discuss the function of the algorithms involved.

    A fuzzy finder like `fzf`. This type of program needs to perform string
    similarity analysis over any input provided and provide results as the
    person types letters to reduce the total size of eligible results.

1.2-2: Suppose we are comparing implementations of insertion sort and merge sort
on the same machine. For inputs of size `n`, insertion sort runs in `8n^2`
steps, while merge sort runs in `64nlg(n)` steps. For which values of `n` does
insertion sort beat merge sort?


    The following program produces a result of '44'.

    ```golang
    func main() {
      fmt.Println("n,isort,msort")

      for n := 2.0; n < 1000.0; n++ {
        isort := 8 * math.Pow(n, 2)
        msort := 64 * (n * math.Log2(n))

        fmt.Printf("%v,%v,%v\n", n, isort, msort)
        if isort > msort {
          break
        }
      }
    }
    ```

    ``csv
    n,isort,msort
    2,32,128
    3,72,304.312800138462
    4,128,512
    5,200,743.0169903639559
    6,288,992.6256002769239
    7,392,1257.6950050818066
    8,512,1536
    9,648,1825.876800830772
    10,800,2126.033980727912
    11,968,2435.439859520657
    12,1152,2753.251200553848
    13,1352,3078.7658454933885
    14,1568,3411.390010163613
    15,1800,3750.614971784178
    16,2048,4096
    17,2312,4447.159571280369
    18,2592,4803.753601661543
    19,2888,5165.4798563474
    20,3200,5532.067961455824
    21,3528,5903.274616214654
    22,3872,6278.879719041314
    23,4232,6658.683199315923
    24,4608,7042.502401107696
    25,5000,7430.169903639559
    26,5408,7821.531690986777
    27,5832,8216.445603738473
    28,6272,8614.780020327225
    29,6728,9016.412726956773
    30,7200,9421.229943568356
    31,7688,9829.12547980756
    32,8192,10240
    33,8712,10653.760380085054
    34,9248,11070.319142560738
    35,9800,11489.593957956724
    36,10368,11911.507203323086
    37,10952,12335.985569809354
    38,11552,12762.9597126948
    39,12168,13192.363938280172
    40,12800,13624.135922911648
    41,13448,14058.216460117852
    42,14112,14494.549232429308
    43,14792,14933.080604940173
    44,15488,15373.759438082629
    ```

1.2-3: What is the smallest value of `n` such that an algorithm whose running
time is 100n^2 runs faster than an algorithm whose running time is 2^n on the
same machine?

    15. Calculated using:

    ```golang
    func main() {
      fmt.Println("n,100n^2,2^n")

      for n := 1.0; n < 100; n++ {
        x := 100 * math.Pow(n, 2)
        y := math.Pow(2, n)

        fmt.Printf("%v,%v,%v\n", n, x, y)

        if x < y {
          break
        }
      }
    }
    ```

    ```csv
    n,100n^2,2^n
    1,100,2
    2,400,4
    3,900,8
    4,1600,16
    5,2500,32
    6,3600,64
    7,4900,128
    8,6400,256
    9,8100,512
    10,10000,1024
    11,12100,2048
    12,14400,4096
    13,16900,8192
    14,19600,16384
    15,22500,32768
    ```

Problem 1-1: Comparison of running times
  For each function `f(n)` and time `t` in the following table, determine the
  largest size `n` of a problem that can be solved in time `t`, assuming that
  the algorithm to solve the problem takes `f(n)` microseconds.

    1 second = 1,000,000 microseconds
    1 minute = 60 seconds = 60,000,000 microseconds
    1 hour = 60 minutes = 3600 seconds = 3,600,000,000 microseconds
    1 day = 24 hours = 1440 mins = 86400 seconds =  86,400,000,000 microseconds

    ```plaintext
    |         | 1 second | 1 minute    | 1 hour        | 1 day          |
    | lg n    | 2^(10^6) | 2^(60*10^6) | 2^(3600*10^6) | 2^(86400*10^6) |
    | sqrt(n) |          |             |               |                |
    | n       | 10^6     | 60*10^6     | 3600*10^6     | 86400*10^6     |
    | nlg(n)  |          |             |               |                |
    | n^2     |          |             |               |                |
    | n^3     |          |             |               |                |
    | 2^n     |          |             |               |                |
    | n!      |          |             |               |                |
    ```

# Chapter 2 Getting Started


2.1 Insertion Sort

Solves the sorting problem.

Input: A sequence of `n` numbers `{a1,a2,...,aN}`
Output: A permutation (reordering) of the input sequence such that: 

  `{a1 <= a2 <= ... <= aN}`

The numbers that we want to sort are known as keys.

e.g.

```plaintext

a. [5, 2, 4, 6, 1, 3]
    x  i
b. [2, 5, 4, 6, 1, 3]
    x  x  i
c. [2, 4, 5, 6, 1, 3]
    x  x  x  i
d. [2, 4, 5, 6, 1, 3]
    x  x  x  x  i
e. [1, 2, 4, 5, 6, 3]
    x  x  x  x  x  i
f. [1, 2, 3, 4, 5, 6]
```

```plaintext
A = {5,2,4,6,1,3}

for j = 2 to A.length
  key = A[j]
  i = j - 1
  while i > 0 and A[i] > key
    A[i+1] = A[i]
    i = i - 1
  A[i+1] = key
```

Loop invariants:

* initializtion: it is true prior to the first iteration of the loop.
* maintenance: if it is true before an iteration of the loop, it remains true
  before the next iteration.
* termination: when the loop terminates, the invariant gives us a useful
  property that helps show that the algorithm is correct.

Similar to mathematical induction, where to prove that a property holds, you
prove a base case and an inductive step.


Pseudocode conventions:

* Indentation indicates block structure
* Looping constructs `while`, `for`, and `repeat-until` and `if-else`
  conditional construct have interpretations similar to those in C.
* compound data is organized into objects which are composed of attributes.

2.1-1: Illustrate the operation of INSERTION-SORT on the array `A = {31,41,59,26,41,58}`

```plaintext
a. [31, 41, 59, 26, 41, 58]
     x   i
b. [31, 41, 59, 26, 41, 58]
     x   x   i
c. [31, 41, 59, 26, 41, 58]
     x   x   x   i
d. [26, 31, 41, 59, 41, 58]
     x   x   x   x   i
e. [26, 31, 41, 41, 59, 58]
     x   x   x   x   x   i
e. [26, 31, 41, 41, 58, 59]
     x   x   x   x   x   x
```

2.1-2: Rewrite the INSERTION-SORT procedure to sort into non-increasing instead
of non-decreasing order.

* non-increasing: descending
* non-decreasing: ascending

```plaintext
for j = 2 to A.length
  key = A[j]
  i = j - 1
  while i > 0 and A[i] < key
    A[i+1] = A[i]
    i = i - 1
  A[i+1] = key
```

2.1-3: Consider the **searching problem:**

Input: A sequence of `n` numbers `A = {a1,a2,...,aN}` and a value `v`.
Output: An index `i` such that `v = A[i]` or the special value `NIL` if `v` does
not appear in `A`.

Write pseudocode for `linear search`, which scans through the sequence, looking
for `v`. Using a loop invariant, prove that your algorithm is correct. Make sure
that your loop invariant fulfills the three necessary properties.

```plaintext
i = 0
for i < A.length and v != A[i]
  i = i + 1
  if i >= A.length
    return NIL

return i
```

* initialization: initialize `i` to first index of first element
* maintenance: continue looping if `i` is less than size of `A` and `A[i]` is
  not equal to the target value `v`.
* termination: terminate loop when the key matches the target value.

2.1-4:

Consider the problem of adding two `n-bit` binary integers, stored in two
`n-element` arrays `A` and `B`. The sum of the two integers should be stored in
binary form in an `(n + 1)-element` array `C`. State the problem formally and
write pseudocode for adding two integers.

Input: Two sequences of `n` numbers `A = {a1,a2,...aN}` and `B = {b1,b2,...,bN}`
Output: A sequence `C` with `n+1` numbers such that `C = {a1+b1,a2+b2,...,aN+bN}`

```plaintext
i = 0
max = 2 ** A.length
for i < A.length
  C[i] = A[i] + B[i]
```

## 2.2 Analyzing Algorithms

Analyzing an algorithm has come to mean predicting the resources that the
algorithm requires.

* memory
* communication bandwith
* computer hardware


Assume a generic one-processor, **random-access machine (RAM)** model of
computation as our implementation.

In the RAM model, instructions are executed one after another, with no
concurrent operations.


Analysis of insertion sort

The time taken by INSERTION-SORT procedure depends on the input; sortin 1k
numbers takes longer than 3 numbers.

In general the time taken by an algorithm grows with the size of the input, so
it is traditional to describe the running time of a program as a function of the
size of its input.

To do so we need to define "running time" and "size of input" more carefully.

* input size: `n`
* running time: number of steps executed.

One line may take a different amount of time than another line, but we shall
assume that each execution of `i`th line takes time c`i`, where c`i` is a constant.

```plaintext
INSERTION-SORT(A)                  | cost | times    |
===================================|======|==========|
for j = 2 to A.length              | c1   | n        |
  key = A[j]                       | c2   | n-1      |
  i = j - 1                        | c3   | n-1      |
                                   |      |----------|
                                   |      | n        |
  while i > 0 and A[i] > key       | c4   | Σ tj     |
                                   |      | j=2      |
                                   |      |----------|
                                   |      | n        |
    A[i + 1] = A[i]                | c5   | Σ (tj-1) |
                                   |      | j=2      |
                                   |      |----------|
                                   |      | n
    i = i - 1                      | c6   | Σ (tj-1) |
                                   |      | j=2      |
                                   |      |----------|
  A[i+1] = key                     | c7   | n -1     |
===================================|======|==========|
```

The running time is the s um of the running times for each statement executed;
a statement that takes `cᵢ` steps to execute and executes `n` times will
contribute `cᵢn` to the total running time.

To compute `T(n)`, the running time of INSERTION-SORT on an input of `n` values,
we sum the sum products of the **cost** and **times** columns.

```plaintext
                                    n         n               n
T(n) = c1n + c2(n-1) + c4(n-1) + c4 Σ tj + c5 Σ (tj - 1) + c6 Σ (tj - 1) + c7(n-1)
                                    j=2       j=2             j=2
```

Reasons for finding worst case running time.

* upper bound on the running time for any input.
* worst case occurs fairly often.
* average case is roughly as bad as the worst case.

Order of growth

We consider only the leading term of a formula since the lower-order terms are
relatively insignificant for large values of `n`. We also ignore the leading
term's constant coefficient, since constant factors are less significant than
the rate of growth in determining computational efficiency for large inputs.

"theta of n-squared"

2.2-1: Express the function n^3 / 1000n^2 - 100n + 3 in terms of 𝚯-notation (theta of n notation)

    * n^3 / 1000n^2 - 100n + 3
    * n^3 - n^2 - n ; drop lower order terms
    = 𝚯(n^3).

2.2-2

> Consider sorting `n` numbers stored in array `A` by first finding the smallest
> element of `A` and exchanging it with the element in `A[1]`. Then find the
> second smallest element of `A`, and exchange it with `A[2]`. Continue in this
> manner for the first `n - 1` elements of `A`.

    Write pseudocode for *selection sort*.

      n = A.length
      for i = 1 to n - 1 {
        min = i
        for j = i + 1 to n {
          if A[j] < A[min]
            min = j
        A[i], A[min] = A[min], A[i]


    What loop invariant does this algorithm maintain?

      * intialization: inner loop initializes to the right index of the outer loop
      * maintenance: with the inner right array of the outer array.
      * termination: when end of loop is reached

    Why does it need to run for only the first n-1 elements, rather than for all `n` elements?

      * The last element of the array should has nothing to be compared against.

    Give the best-case and worst-case running times of selection sort in 𝚯-notation.

      = 𝚯(n^2). two loops, one nested within the other.

2.2-3:

> Consider linear search again (see Exercise 2.1-3). How many elements of the
> input sequence need to be checked on the average, assuming that the element
> being searched for is equally likely to be any element in the array? How about
> in the worst case? What are the average-case and worst-case running times of
> linear search in 𝚯-notation? Justify your answers.

    How many elements of the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to be any element in the array?

      Since there are `n` elements the average would be in the middle (.i.e. n/2).
      When we drop the lower order terms this becomes `𝚯(n)`.

    How about in the worst case?

      = 𝚯(n). In the worst case you need to search check every element in the input.

    What are the average-case and worst-case running times of linear search in 𝚯-notation?

      They are both 𝚯(n).

2.2-4: How can we modify almost any algorithm to have a good best-case running time?

    Reduce the input size by rejecting elements or hard code an early return if some condition is satisfied.

    Check for some particular input and if it receives that then returns some
    answer. i.e. cheating. Slow algorithm that works fast on some input.

[Watch](http://freevideolectures.com/Course/1941/Introduction-to-Algorithms/1)

* Performance
* User friendliness

Algorithms give you a language to talk about language behaviour.

# 2.3 - Designing algorithms


algorithm design techniques:

* incremental approach (insertion sort)
* divide and conquer

2.3.1 - The divide-and-conquer approach

they break the problem down into several subproblems that are similar to the original
problem but smaller in size, solve the subproblems recursively, and then combine
these solutions to creat a solution the original problem.

Involves three steps at each level of the recursion:

1. Divide: the problem into a number of subproblems that are all smaller
   instances of the same problem.
1. Conquer: the subproblems by solving them recursively. If the subproblem sizes
   are small enough, however, just solve the subproblems in a straightforward
   manner.
1. Combine: the solutions to the subproblems into the solution for the original
   problem.

The `merge sort` algorithm closely follows the divide-and-conquer paradigm.

* Divide: dive the `n`-element sequence to be sorted into two subsequences of
  `n/2` elements each.
* Conquer: Sort the two subsequences to produce the sorted answer.
* Combine: Merge the two sorted subsequences to produce the sorted answer.

The recursion "bottoms out" when the sequence to be sorted has length 1.
Every sequence with length 1 is already sorted.

The key operation of merge sort is mergin two sorted sequences in the
"combine" step.

`MERGE(A, p, q, r)` where `A` is an array and `p`, `q`, and `r` are indices into
the array such that `p <= q < r`.

Merging takes `𝚯(n)` time.

```plaintext
MERGE(A, p, q, r)

n1 = q - p + 1
n2 = r - q
let L[1..n1+1] and R[1..n2+1] be new arrays
for i = 1 to n1
  L[i] = A[p+i-1]
for j = 1 to n2
  R[j] = A[q+j]
L[n1+1] = ∞
R[n2+1] = ∞
i = 1
j = 1
for k = p to r
  if L[i] <= R[j]
    A[k] = L[i]
    i = i + 1
  else A[k] = R[j]
    j = j + 1
```

```plaintext
A: [2, 4, 5, 7, 1, 2, 3, 6]
    k
L: [2, 4, 5, 7, ∞]
    i
R: [1, 2, 3, 6, ∞]
    j

A: [1, 4, 5, 7, 1, 2, 3, 6]
       k
L: [2, 4, 5, 7, ∞]
    i
R: [1, 2, 3, 6, ∞]
       j

A: [1, 2, 5, 7, 1, 2, 3, 6]
          k
L: [2, 4, 5, 7, ∞]
       i
R: [1, 2, 3, 6, ∞]
       j

A: [1, 2, 2, 7, 1, 2, 3, 6]
             k
L: [2, 4, 5, 7, ∞]
       i
R: [1, 2, 3, 6, ∞]
          j

A: [1, 2, 2, 3, 1, 2, 3, 6]
                k
L: [2, 4, 5, 7, ∞]
       i
R: [1, 2, 3, 6, ∞]
             j

A: [1, 2, 2, 3, 4, 2, 3, 6]
                   k
L: [2, 4, 5, 7, ∞]
          i
R: [1, 2, 3, 6, ∞]
             j

A: [1, 2, 2, 3, 4, 5, 3, 6]
                      k
L: [2, 4, 5, 7, ∞]
             i
R: [1, 2, 3, 6, ∞]
             j

A: [1, 2, 2, 3, 4, 5, 6, 6]
                         k
L: [2, 4, 5, 7, ∞]
             i
R: [1, 2, 3, 6, ∞]
                j

A: [1, 2, 2, 3, 4, 5, 6, 7]
                            k
L: [2, 4, 5, 7, ∞]
                i
R: [1, 2, 3, 6, ∞]
                j
```

We must show that this loop invariant holds prior to the first iteration of the
`for` loop of lines 12-17, that each iteration of the loop maintains the
invariant, and the invariant provides a useful property to show correctness when
the loop terminates.

Initialization:

Prior to the first iteration we have `k = p`, so that the subarray `A[p..k-1]`
is empty.

```plaintext
for k = p to r
```

Maintenance:

To see that each iteration maintains the loop invariant,
we loop until we have reached the end of both `L` and `R`.

```plaintext
for k = p to r
  if L[i] <= R[j]
    A[k] = L[i]
    i = i + 1
  else
    A[k] = R[j]
    j = j + 1
```

Termination:

When we reach the sentinal value for both L and R we stop.

```
MERGE-SORT(A,p,r)
if p < r
  q = [(p+r)/2]
  MERGE-SORT(A,p,q)
  MERGE-SORT(A,q+1,r)
  MERGE(A,p,q,r)
```

Analyzing divide-and-conquer algorithms

When an algorithm contains a recursive call to itself, we can often describe its
running time by a `recurrence equation` or `recurrence`, which describes the
overall running time on a problem of size `n` in terms of the running time on
smaller inputs.

We can then use mathematical tools to solve the recurrence and provide bounds on
the performance of the algorithm.

```plaintext
Recursion Tree

              -----------------
              |1|2|2|3|4|5|6|7|
              -----------------
              /               \
        ---------           ---------
        |2|4|5|7|           |1|2|3|6|
        ---------           ---------
        /       \           /       \
    -----       -----      -----    -----
    |2|5|       |4|7|      |1|3|    |2|6|
    -----       -----      -----    -----
    /   \       /   \     /   |     /    \
   -     -     -    -    -    -     -    -
  |5|   |2|   |4|  |7|  |1|  |3|   |2|  |6|
   -     -     -    -    -    -     -    -
```

Running time:

`T(n)`

Analysis of merge sort

2.3-1: Using Figure 2.4 as a model, illustrate the operation of merge sort on the array `A = [3,41,52,26,38,57,9,49]`.

```plaintext
              -----------------------
              |3|9|26|38|41|49|52|57|
              -----------------------
               /                  \
      ------------             ------------
      |3|41|52|26|             |38|57|9|49|
      ------------             ------------
      /          \              /         \
    ------     -------       -------     ------
    |3|41|     |52|26|       |38|57|     |9|49|
    ------     -------       -------     ------
   /     \     /      \     /       \    /     \
  -      --   --      --   --       --   -     --
 |3|    |41| |52|    |26| |38|     |57| |9|   |49|
  -      --   --      --   --       --   -     --
```

2.3-2: Rewrite the MERGE procedure so that it does not use sentinels, instead
stopping once either array `L` or `R` has had all its elements copied back to
`A` and then copying the remainder of the other array back into `A`.

```plaintext
MERGE(A, p, q, r)

n1 = q - p + 1
n2 = r - q

for i = 1 to n1
  L[i] = A[p+i-1]

for j = 1 to n2
  R[j] = A[q+j]

i = 1
j = 1
k = p

while i < q and j < r
  if L[i] <= R[j]
    A[k] = L[i]
    i = i + 1
  else
    A[k] = R[j]
    j = j + 1
  k = k + 1

for k = k to r
  if j >= r
    A[k] = L[i]
    i = i + 1
  else
    A[k] = R[j]
    j = j + 1
```

2.3-3: Use mathematical induction to show that when `n` is an exact power of 2,
the solution of the recurrence ... is `T(n) = nlg(n)`

```plaintext
         2            if n = 2
T(n) = { 2T(n/2) + n  if n = 2**k, for k > 1
```

 ???

2.3-4: We can express insertion sort as a recursive procedure as follows In
order to sort `A[i..n]`, we recursively sort `A[i..n-1]` and then insert `A[n]`
into the sorted array `A[1..n-1]`. Write a recurrence for the worst-case running
time of this recursive version of insertion sort.


2.3-5: Referring back to the searching problem (see Exercise 2.1-3), observe that
    if the sequence A is sorted, we can check the midpoint of the sequence
    against v and eliminate half of the sequence from further consideration. The
    binary search algorithm repeats this procedure, halving the size of the
    remaining portion of the sequence each time. Write pseudocode, either
    iterative or recursive, for binary search. Argue that the worst case running
    time of binary search is O(lg(n)).

`BINARY-SEARCH(A, t, s, e)` where `A` is an array and `s`, and `r` are indices into the array such that `s < e` and `t` is the target value to find.

```plaintext
BINARY-SEARCH(A, t, s, e)
  length = e - s
  if length == 1
    item = A[s]
  else
    mid = (length / 2) + s
    item = A[mid]

  if item == t
    return mid
  if item < t
    return BINARY-SEARCH(A, t, s, mid-1)
  else
    return BINARY-SEARCH(A, t, mid+1, e)
```

# Growth of Functions

When we look at input sizes large enough to make only the order of growth of the
running time relevant, we are studying the _asymptotic_ efficiency of
algorithms.


## Asymptotic Notation

Natural numbers. `N = {0,1,2,...}`. This notation is useful for describing the
worst case running time of function `T(n)`.

### 𝚯-notation (theta)

The worst case running time of insertion sort is `T(n) = 𝚯(n^2)`.


`f(n) = O(g(n))` means that there are some suitable constants `c > 0` and `n0 >0`
such that f is bounded by c of g of n for all of n.

Ex.

`2*n^2 = O(n^3)`

big o is like less than or equal to.
set definitiion


`2n^2` is in the set of `O(n^3)`

Macro Convention:
  A set in a formula represents an anonymous function in that set.

Ex. `f(n) = n^3 + O(n^2)`.
  This means that there is a function h(n) that is in big o of n squared such that
  `f(n) = n^3 th(n)`. WHAT... THE WHAT?

Ex. `n^2 + O(n) = O(n^2)`. equals means `is`. is means everything over here means something over here.
Everything on the left exists on the right side, but the right is not the same as
the left side.

Big omega notation. _()_
  _()_(g(n)) = {f(n) there exists consts c > 0


* running time: `𝚯(n)`. Theta of n.
  * When we say that a particular running time is theta of n, we're saying that
    once `n` gets large enough, the running time is at least `k1*n` and at most
    `k2*n` for some constants `k1` and `k2`.
  * we don't have to worry about which time units we're using.
  * when we use big-𝚯 notation, we're saying that we have an *asymptotically tight bound* on the running time.
  * `𝚯(1)`: Constant time.
  * `𝚯(log n)`:
  * `𝚯(n)`:
  * `𝚯(nlog n)`:
  * `𝚯(n^2)`:
  * `𝚯(n^2 * log n)`:
  * `𝚯(n^3)`:
  * `𝚯(2^n)`:
  * `𝚯(n!)`:
* rate of growth


Abdul Bari https://www.youtube.com/watch?v=A03oI0znAoc
Asymptotic Notations Big Oh - Omega - Theta

Representing a simple form of a function

We need a simple method for representing time complexity.

| symbol | english | use |
| -------- | --- | --- |
| O | big-oh | upper bound of a function |
| 𝚯 | theta notation | average bound of a function |
| _()_ | big-omega | lower bound of a function |

Theta is useful.

class of functions

| name          | symbol    | speed |
| ------------- | --------- | ----- |
| constant      | 𝚯(1)      | fast  |
| logarithmic   | 𝚯(log n)  |   |   |
|               | 𝚯(sqrt n) |   |   |
| linear        | 𝚯(n)      |   |   |
|               | 𝚯(n logn) |   |   |
| polynomial    | 𝚯(n^2)    |   |   |
|               | 𝚯(n^3)    |   |   |
| exponential   | 𝚯(2^n)    |   |   |
|               | 𝚯(3^n)    |   |   |
| factorial     | 𝚯(n!)     |   V   |
|               | 𝚯(n^n)    | slow  |

1 < logn < sqrt(n) < n < nlogn < n^2 < n^3 ... < 2^n < 3^n ... < n^n

Big-oh
------

The function `f(n) = O(g(n))` if there exists positive constants `c` and `n0`
such that `0 <= f(n) <= c*g(n)` for all `n >= n0`.

Example:

```
  f(n) = 2n+3
  2n+3 <= __ 10n __ n>=1
  f(n)        c*g(n)
  f(n) = O(n)

  2n+3 <= 2n+3n will always work.
```

instead of guessing the value you can make it as 2n+3

Little-oh
---------

The function `f(n) = o(g(n))` for any positive constant `c > 0`,
if there exists a constant `n0 > 0` such that `0 < f(n) < c * g(n)`
for all `n >= n0`.


Omega
----

The function `f(n) = omega(g(n))` if there exists positive contstants c and n0
such that `0 <= c * g(n) <= f(n)` for all `n >= n0`.

e.g.

```
f(n) = 2n+3
f(n)    c * g(n)

2n+3 >= log n V n>=1
f(n)     c * g(n)


 true f(n) = omega(n)   (most useful answer)
 true f(n) = omega(logn)
```

little-omega w-notation
----------
Denotes a lower bound that is not asymptotically tight.

The function `f(n) = w(g(n))` for any positive constant `c > 0`,
if there exists a constant `n0 > 0`
such that `0 <= c * g(n) < f(n)` for all `n >= n0`

the relation `f(n) = w(g(n))` implies that:

```plaintext
lim         f(n)
            ---- = infinity
n->infinity g(n)
```
if the limit exists. That is `f(n)` becomes arbitrarily large relative to `g(n)`
as `n` approaches infinity.


Theta
-----

The function `f(n)=theta(g(n))` if there exists positive constants c1, c2, and n0
such that `0 <= c1 * g(n) <= f(n) <= c2 * g(n)` for all `n >= n0`. (n0 is pronounced enn-not)

f(n) = theta(g(n))

```
eg.
f(n) = 2n + 3
1*n   <= 2n + 3 <= 5xn
c*g(n)   f(n)
```

omega <= theta <= big-oh

| omega | theta | big-oh |
| ----- | ----- | ------ |
| omega(1) | | O(n^n) |
| omega(1) | theta(log n!) | O(nlog n) |

1 < logn < sqrt(n) < n < nlogn < n^2 < n^3 ... < 2^n < 3^n ... < n^n


constant (1)
========

```bash
モ ruby -e '1.upto(100) { |n| puts 10 }' | asciigraph -h 32 -w 72
 10.00 ┼───────────────────────────────────────────────────────────────────────
```

logarithmic (logn)
===========

```bash
モ ruby -e '1.upto(100) { |n| puts Math.log2(n) }' | asciigraph -h 32 -w 72
 6.64 ┼                                                                  ╭────
 6.44 ┤                                                         ╭────────╯
 6.23 ┤                                                 ╭───────╯
 6.02 ┤                                          ╭──────╯
 5.81 ┤                                    ╭─────╯
 5.61 ┤                               ╭────╯
 5.40 ┤                           ╭───╯
 5.19 ┤                       ╭───╯
 4.98 ┤                    ╭──╯
 4.78 ┤                 ╭──╯
 4.57 ┤               ╭─╯
 4.36 ┤            ╭──╯
 4.15 ┤           ╭╯
 3.94 ┤         ╭─╯
 3.74 ┤        ╭╯
 3.53 ┤      ╭─╯
 3.32 ┤     ╭╯
 3.11 ┤     │
 2.91 ┤    ╭╯
 2.70 ┤   ╭╯
 2.49 ┤   │
 2.28 ┤  ╭╯
 2.08 ┤  │
 1.87 ┤ ╭╯
 1.66 ┤ │
 1.45 ┤ │
 1.25 ┤╭╯
 1.04 ┤│
 0.83 ┤│
 0.62 ┤│
 0.42 ┤│
 0.21 ┤│
 0.00 ┼╯
```

square root (n)
===============

```bash
モ ruby -e '1.upto(100) { |n| puts Math.sqrt(n) }' | asciigraph -h 32 -w 72
 10.00 ┤                                                                      ╭
  9.72 ┤                                                                  ╭───╯
  9.44 ┤                                                              ╭───╯
  9.16 ┤                                                           ╭──╯
  8.88 ┤                                                       ╭───╯
  8.59 ┤                                                    ╭──╯
  8.31 ┤                                                ╭───╯
  8.03 ┤                                             ╭──╯
  7.75 ┤                                          ╭──╯
  7.47 ┤                                       ╭──╯
  7.19 ┤                                    ╭──╯
  6.91 ┤                                 ╭──╯
  6.62 ┤                              ╭──╯
  6.34 ┤                            ╭─╯
  6.06 ┤                         ╭──╯
  5.78 ┤                       ╭─╯
  5.50 ┤                    ╭──╯
  5.22 ┤                  ╭─╯
  4.94 ┤                ╭─╯
  4.66 ┤              ╭─╯
  4.38 ┤            ╭─╯
  4.09 ┤           ╭╯
  3.81 ┤         ╭─╯
  3.53 ┤        ╭╯
  3.25 ┤      ╭─╯
  2.97 ┤     ╭╯
  2.69 ┤    ╭╯
  2.41 ┤   ╭╯
  2.12 ┤  ╭╯
  1.84 ┤ ╭╯
  1.56 ┤ │
  1.28 ┤╭╯
  1.00 ┼╯
```

Linear (n)
=========

```bash
 100.00 ┼                                                                     ╭─
  96.91 ┤                                                                  ╭──╯
  93.81 ┤                                                                ╭─╯
  90.72 ┤                                                              ╭─╯
  87.62 ┤                                                            ╭─╯
  84.53 ┤                                                          ╭─╯
  81.44 ┤                                                       ╭──╯
  78.34 ┤                                                     ╭─╯
  75.25 ┤                                                   ╭─╯
  72.16 ┤                                                 ╭─╯
  69.06 ┤                                              ╭──╯
  65.97 ┤                                            ╭─╯
  62.88 ┤                                          ╭─╯
  59.78 ┤                                        ╭─╯
  56.69 ┤                                      ╭─╯
  53.59 ┤                                   ╭──╯
  50.50 ┤                                 ╭─╯
  47.41 ┤                               ╭─╯
  44.31 ┤                             ╭─╯
  41.22 ┤                           ╭─╯
  38.12 ┤                        ╭──╯
  35.03 ┤                      ╭─╯
  31.94 ┤                    ╭─╯
  28.84 ┤                  ╭─╯
  25.75 ┤               ╭──╯
  22.66 ┤             ╭─╯
  19.56 ┤           ╭─╯
  16.47 ┤         ╭─╯
  13.38 ┤       ╭─╯
  10.28 ┤    ╭──╯
   7.19 ┤  ╭─╯
   4.09 ┤╭─╯
   1.00 ┼╯
```



n log(n)
========

```bash
モ ruby -e '1.upto(100) { |n| puts n * Math.log2(n) }' | asciigraph -h 32 -w 72
 664 ┼                                                                      ╭
 644 ┤                                                                    ╭─╯
 623 ┤                                                                  ╭─╯
 602 ┤                                                                ╭─╯
 581 ┤                                                              ╭─╯
 561 ┤                                                            ╭─╯
 540 ┤                                                          ╭─╯
 519 ┤                                                        ╭─╯
 498 ┤                                                       ╭╯
 478 ┤                                                     ╭─╯
 457 ┤                                                   ╭─╯
 436 ┤                                                 ╭─╯
 415 ┤                                               ╭─╯
 394 ┤                                             ╭─╯
 374 ┤                                           ╭─╯
 353 ┤                                         ╭─╯
 332 ┤                                       ╭─╯
 311 ┤                                     ╭─╯
 291 ┤                                  ╭──╯
 270 ┤                                ╭─╯
 249 ┤                              ╭─╯
 228 ┤                            ╭─╯
 208 ┤                          ╭─╯
 187 ┤                        ╭─╯
 166 ┤                     ╭──╯
 145 ┤                   ╭─╯
 125 ┤                ╭──╯
 104 ┤              ╭─╯
  83 ┤           ╭──╯
  62 ┤         ╭─╯
  42 ┤      ╭──╯
  21 ┤  ╭───╯
   0 ┼──╯
```

n^2
===

```bash
 10000 ┼                                                                      ╭
  9688 ┤                                                                     ╭╯
  9375 ┤                                                                    ╭╯
  9063 ┤                                                                  ╭─╯
  8750 ┤                                                                 ╭╯
  8438 ┤                                                                ╭╯
  8125 ┤                                                               ╭╯
  7813 ┤                                                              ╭╯
  7500 ┤                                                            ╭─╯
  7188 ┤                                                           ╭╯
  6875 ┤                                                          ╭╯
  6563 ┤                                                        ╭─╯
  6250 ┤                                                       ╭╯
  5938 ┤                                                     ╭─╯
  5625 ┤                                                    ╭╯
  5313 ┤                                                  ╭─╯
  5000 ┤                                                 ╭╯
  4688 ┤                                               ╭─╯
  4376 ┤                                             ╭─╯
  4063 ┤                                            ╭╯
  3751 ┤                                          ╭─╯
  3438 ┤                                        ╭─╯
  3126 ┤                                      ╭─╯
  2813 ┤                                    ╭─╯
  2501 ┤                                 ╭──╯
  2188 ┤                               ╭─╯
  1876 ┤                             ╭─╯
  1563 ┤                          ╭──╯
  1251 ┤                      ╭───╯
   938 ┤                   ╭──╯
   626 ┤              ╭────╯
   313 ┤        ╭─────╯
     1 ┼────────╯
```

n^3
===

```bash
モ ruby -e '1.upto(100) { |n| puts n ** 3 }' | asciigraph -h 32 -w 72
 1000000 ┼                                                                      ╭
  968750 ┤                                                                     ╭╯
  937500 ┤                                                                     │
  906250 ┤                                                                    ╭╯
  875000 ┤                                                                   ╭╯
  843750 ┤                                                                  ╭╯
  812500 ┤                                                                 ╭╯
  781250 ┤                                                                ╭╯
  750000 ┤                                                               ╭╯
  718750 ┤                                                               │
  687500 ┤                                                              ╭╯
  656250 ┤                                                             ╭╯
  625000 ┤                                                            ╭╯
  593750 ┤                                                           ╭╯
  562500 ┤                                                         ╭─╯
  531250 ┤                                                        ╭╯
  500000 ┤                                                       ╭╯
  468751 ┤                                                      ╭╯
  437501 ┤                                                     ╭╯
  406251 ┤                                                   ╭─╯
  375001 ┤                                                  ╭╯
  343751 ┤                                                ╭─╯
  312501 ┤                                               ╭╯
  281251 ┤                                             ╭─╯
  250001 ┤                                           ╭─╯
  218751 ┤                                         ╭─╯
  187501 ┤                                       ╭─╯
  156251 ┤                                    ╭──╯
  125001 ┤                                 ╭──╯
   93751 ┤                             ╭───╯
   62501 ┤                         ╭───╯
   31251 ┤                 ╭───────╯
       1 ┼─────────────────╯
```

2^n
===

```bash
モ ruby -e '1.upto(100) { |n| puts 2 ** n }' | asciigraph -h 32 -w 72
 1267650600228229401496703205376 ┼                                                                      ╭
 1228036518971097232699931230208 ┤                                                                      │
 1188422437713965063903159255040 ┤                                                                      │
 1148808356456832895106387279872 ┤                                                                      │
 1109194275199700726309615304704 ┤                                                                      │
 1069580193942568557512843329536 ┤                                                                      │
 1029966112685436388716071354368 ┤                                                                      │
  990352031428304219919299379200 ┤                                                                      │
  950737950171172051122527404032 ┤                                                                      │
  911123868914039882325755428864 ┤                                                                      │
  871509787656907713528983453696 ┤                                                                      │
  831895706399775544732211478528 ┤                                                                      │
  792281625142643375935439503360 ┤                                                                      │
  752667543885511207138667528192 ┤                                                                      │
  713053462628379038341895553024 ┤                                                                      │
  673439381371246869545123577856 ┤                                                                      │
  633825300114114700748351602688 ┤                                                                      │
  594211218856982531951579627520 ┤                                                                      │
  554597137599850363154807652352 ┤                                                                      │
  514983056342718194358035677184 ┤                                                                     ╭╯
  475368975085586025561263702016 ┤                                                                     │
  435754893828453856764491726848 ┤                                                                     │
  396140812571321687967719751680 ┤                                                                     │
  356526731314189519170947776512 ┤                                                                     │
  316912650057057350374175801344 ┤                                                                     │
  277298568799925181577403826176 ┤                                                                     │
  237684487542793012780631851008 ┤                                                                     │
  198070406285660843983859875840 ┤                                                                    ╭╯
  158456325028528675187087900672 ┤                                                                    │
  118842243771396506390315925504 ┤                                                                    │
   79228162514264337593543950336 ┤                                                                   ╭╯
   39614081257132168796771975168 ┤                                                                  ╭╯
                               0 ┼──────────────────────────────────────────────────────────────────╯
```

3^n
===

```bash
モ ruby -e '1.upto(100) { |n| puts 3 ** n }' | asciigraph -h 32 -w 72
 515377520732011324194596268868618440852459487232 ┼                                                                      ╭
 499271973209135955101707932727721296615381663744 ┤                                                                      │
 483166425686260586008819596586824152378303840256 ┤                                                                      │
 467060878163385298045569675052608703930231160832 ┤                                                                      │
 450955330640509928952681338911711559693153337344 ┤                                                                      │
 434849783117634559859793002770814415456075513856 ┤                                                                      │
 418744235594759190766904666629917271218997690368 ┤                                                                      │
 402638688071883821674016330489020126981919866880 ┤                                                                      │
 386533140549008533710766408954804678533847187456 ┤                                                                      │
 370427593026133164617878072813907534296769363968 ┤                                                                      │
 354322045503257795524989736673010390059691540480 ┤                                                                      │
 338216497980382426432101400532113245822613716992 ┤                                                                      │
 322110950457507057339213064391216101585535893504 ┤                                                                      │
 306005402934631728811143935553659805242960642048 ┤                                                                      │
 289899855411756359718255599412762661005882818560 ┤                                                                      │
 273794307888881031190186470575206364663307567104 ┤                                                                      │
 257688760366005662097298134434309220426229743616 ┤                                                                      │
 241583212843130293004409798293412076189151920128 ┤                                                                      │
 225477665320254964476340669455855779846576668672 ┤                                                                      │
 209372117797379595383452333314958635609498845184 ┤                                                                      │
 193266570274504266855383204477402339266923593728 ┤                                                                      │
 177161022751628897762494868336505195029845770240 ┤                                                                      │
 161055475228753528669606532195608050792767946752 ┤                                                                      │
 144949927705878159576718196054710906555690123264 ┤                                                                      │
 128844380183002790483829859913813762318612299776 ┤                                                                     ╭╯
 112738832660127502520579938379598313870539620352 ┤                                                                     │
  96633285137252133427691602238701169633461796864 ┤                                                                     │
  80527737614376764334803266097804025396383973376 ┤                                                                     │
  64422190091501395241914929956906881159306149888 ┤                                                                     │
  48316642568626026149026593816009736922228326400 ┤                                                                     │
  32211095045750738185776672281794288474155646976 ┤                                                                    ╭╯
  16105547522875369092888336140897144237077823488 ┤                                                                    │
                                                0 ┼────────────────────────────────────────────────────────────────────╯
```

factorial
=========

```bash
モ ruby -e '1.upto(100) { |n| puts (1..n).reduce(:*) || 1 }' | asciigraph -h 32 -w 72
 93326215443944150965646704795953882578400970373184098831012889540582227238570431295066113089288327277825849664006524270554535976289719382852181865895959724032 ┼                                                                      ╭
 90409771211320894723678960937099742018530417689077610513736049894308587881917371125019252709659385351025577475535631344215463015406338066470094307934227922944 ┤                                                                      │
 87493326978697638481711217078245601458659865004971122196459210248034948525264310954972392330030443424225305287064738417876390054522956750088006749972496121856 ┤                                                                      │
 84576882746074382239743473219391460898789312320864633879182370601761309168611250784925531950401501497425033098593845491537317093639575433705919192010764320768 ┤                                                                      │
 81660438513451125997775729360537320338918759636758145561905530955487669811958190614878671570772559570624760910122952565198244132756194117323831634049032519680 ┤                                                                      │
 78743994280827881950138260173527833613412385832207539075090186094257588498887003981440165955853071238770203813417571981933120864867433486285399073307165196288 ┤                                                                      │
 75827550048204625708170516314673693053541833148101050757813346447983949142233943811393305576224129311969931624946679055594047903984052169903311515345433395200 ┤                                                                      │
 72911105815581369466202772455819552493671280463994562440536506801710309785580883641346445196595187385169659436475786129254974943100670853521223957383701594112 ┤                                                                      │
 69994661582958113224235028596965411933800727779888074123259667155436670428927823471299584816966245458369387248004893202915901982217289537139136399421969793024 ┤                                                                      │
 67078217350334856982267284738111271373930175095781585805982827509163031072274763301252724437337303531569115059534000276576829021333908220757048841460237991936 ┤                                                                      │
 64161773117711600740299540879257130814059622411675097488705987862889391715621703131205864057708361604768842871063107350237756060450526904374961283498506190848 ┤                                                                      │
 61245328885088344498331797020402990254189069727568609171429148216615752358968642961159003678079419677968570682592214423898683099567145587992873725536774389760 ┤                                                                      │
 58328884652465100450694327833393503528682695923018002684613803355385671045897456327720498063159931346114013585886833840633559831678384956954441164794907066368 ┤                                                                      │
 55412440419841832014396309302694709134447964359355632536875468924068473645662522621065282918821535824368026305650428571220537177800382955228698609613310787584 ┤                                                                      │
 52495996187218587966758840115685222408941590554805026050060124062838392332591335987626777303902047492513469208945047987955413909911622324190266048871443464192 ┤                                                                      │
 49579551954595331724791096256831081849071037870698537732783284416564752975938275817579916924273105565713197020474155061616340949028241007808178490909711663104 ┤                                                                      │
 46663107721972075482823352397976941289200485186592049415506444770291113619285215647533056544644163638912924832003262135277267988144859691426090932947979862016 ┤                                                                      │
 43746663489348819240855608539122800729329932502485561098229605124017474262632155477486196165015221712112652643532369208938195027261478375044003374986248060928 ┤                                                                      │
 40830219256725562998887864680268660169459379818379072780952765477743834905979095307439335785386279785312380455061476282599122066378097058661915817024516259840 ┤                                                                      │
 37913775024102306756920120821414519609588827134272584463675925831470195549326035137392475405757337858512108266590583356260049105494715742279828259062784458752 ┤                                                                      │
 34997330791479050514952376962560379049718274450166096146399086185196556192672974967345615026128395931711836078119690429920976144611334425897740701101052657664 ┤                                                                      │
 32080886558855806467314907775550892324211900645615489659583741323966474879601788333907109411208907599857278981414309846655852876722573794859308140359185334272 ┤                                                                      │
 29164442326232550225347163916696751764341347961509001342306901677692835522948728163860249031579965673057006792943416920316779915839192478477220582397453533184 ┤                                                                      │
 26247998093609293983379420057842611204470795277402513025030062031419196166295667993813388651951023746256734604472523993977706954955811162095133024435721732096 ┤                                                                      │
 23331553860986037741411676198988470644600242593296024707753222385145556809642607823766528272322081819456462416001631067638633994072429845713045466473989931008 ┤                                                                      │
 20415109628362781499443932340134330084729689909189536390476382738871917452989547653719667892693139892656190227530738141299561033189048529330957908512258129920 ┤                                                                      │
 17498665395739525257476188481280189524859137225083048073199543092598278096336487483672807513064197965855918039059845214960488072305667212948870350550526328832 ┤                                                                      │
 14582221163116269015508444622426048964988584540976559755922703446324638739683427313625947133435256039055645850588952288621415111422285896566782792588794527744 ┤                                                                      │
 11665776930493024967870975435416562239482210736425953269107358585094557426612240680187441518515767707201088753883571705356291843533525265528350231846927204352 ┤                                                                      │
  8749332697869768725903231576562421679611658052319464951830518938820918069959180510140581138886825780400816565412678779017218882650143949146262673885195403264 ┤                                                                      │
  5832888465246512483935487717708281119741105368212976634553679292547278713306120340093720759257883853600544376941785852678145921766762632764175115923463602176 ┤                                                                      │
  2916444232623256241967743858854140559870552684106488317276839646273639356653060170046860379628941926800272188470892926339072960883381316382087557961731801088 ┤                                                                      │
                                                                                                                                                              0 ┼──────────────────────────────────────────────────────────────────────╯
```

n^n
===

```bash
モ ruby -e '1.upto(100) { |n| puts n ** n }' | asciigraph -h 32 -w 72
 99999999999999996973312221251036165947450327545502362648241750950346848435554075534196338404706251868027512415973882408182135734368278484639385041047239877871023591066789981811181813306167128854888448 ┼                                                                      ╭
 96874999999999993881068257436338693624063265494893649837925489870956970225278181471331343664445725062176639061598984569590467075190263689914928232598270195230434231246428683216594756627990091887804416 ┤                                                                      │
 93749999999999990788824293621641221300676203444284937027609228791567092015002287408466348924185198256325765707224086730998798416012248895190471424149300512589844871426067384622007699949813054920720384 ┤                                                                      │
 90625000000000004692996099943490907044111751072672298764272734977198756186938815758515269731196439103674964840186330296865673316722266591556553420586962491053894832136501348230021310004219026968936448 ┤                                                                      │
 87500000000000001600752136128793434720724689022063585953956473897808877976662921695650274990935912297824091485811432458274004657544251796832096612137992808413305472316140049635434253326041990001852416 ┤                                                                      │
 84374999999999998508508172314095962397337626971454873143640212818418999766387027632785280250675385491973218131436534619682335998366237002107639803689023125772716112495778751040847196647864953034768384 ┤                                                                      │
 81249999999999995416264208499398490073950564920846160333323951739029121556111133569920285510414858686122344777061636781090667339188222207383182995240053443132126752675417452446260139969687916067684352 ┤                                                                      │
 78124999999999992324020244684701017750563502870237447523007690659639243345835239507055290770154331880271471422686738942498998680010207412658726186791083760491537392855056153851673083291510879100600320 ┤                                                                      │
 74999999999999997729984165938277124460587745659126771986181313212760136326665556650647253803529688901020634311980411806136601800776208863479538780785429908403267693300092486358386359979625346641166336 ┤                                                                      │
 71875000000000003135948087191853231170611988448016096449354935765881029307495873794239216836905045921769797201274084669774204921542210314300351374779776056314997993745128818865099636667739814181732352 ┤                                                                      │
 68750000000000000043704123377155758847224926397407383639038674686491151097219979731374222096644519115918923846899186831182536262364195519575894566330806373674408633924767520270512579989562777214648320 ┤                                                                      │
 65624999999999996951460159562458286523837864346798670828722413607101272886944085668509227356383992310068050492524288992590867603186180724851437757881836691033819274104406221675925523311385740247564288 ┤                                                                      │
 62499999999999993859216195747760814200450802296189958018406152527711394676668191605644232616123465504217177138149391153999198944008165930126980949432867008393229914284044923081338466633208703280480256 ┤                                                                      │
 59374999999999999265180117001336920910475045085079282481579775080832287657498508749236195649498822524966340027443064017636802064774167380947793543427213156304960214729081255588051743321323170821046272 ┤                                                                      │
 56249999999999996172936153186639448587087983034470569671263514001442409447222614686371200909238295719115466673068166179045133405596152586223336734978243473664370854908719956993464686643146133853962240 ┤                                                                      │
 53125000000000001578900074440215555297112225823359894134437136554563302428052931829963163942613652739864629562361839042682736526362154037044149328972589621576101155353756289500177963331260601394528256 ┤                                                                      │
 49999999999999998486656110625518082973725163772751181324120875475173424217777037767098169202353125934013756207986941204091067867184139242319692520523619938935511795533394990905590906653083564427444224 ┤                                                                      │
 46874999999999995394412146810820610650338101722142468513804614395783546007501143704233174462092599128162882853612043365499399208006124447595235712074650256294922435713033692311003849974906527460360192 ┤                                                                      │
 43750000000000000800376068064396717360362344511031792976978236948904438988331460847825137495467956148912045742905716229137002328772125898416048306068996404206652736158070024817717126663020995000926208 ┤                                                                      │
 40624999999999997708132104249699245036975282460423080166661975869514560778055566784960142755207429343061172388530818390545333669594111103691591497620026721566063376337708726223130069984843958033842176 ┤                                                                      │
 37500000000000003114096025503275351746999525249312404629835598422635453758885883928552105788582786363810335277824491254182936790360112554512404091614372869477793676782745058729843346672958425574408192 ┤                                                                      │
 34375000000000000021852061688577879423612463198703691819519337343245575548609989865687111048322259557959461923449593415591268131182097759787947283165403186837204316962383760135256289994781388607324160 ┤                                                                      │
 31249999999999996929608097873880407100225401148094979009203076263855697338334095802822116308061732752108588569074695576999599472004082965063490474716433504196614957142022461540669233316604351640240128 ┤                                                                      │
 28125000000000002335572019127456513810249643936984303472376698816976590319164412946414079341437089772857751458368368440637202592770084415884303068710779652108345257587058794047382510004718819180806144 ┤                                                                      │
 24999999999999999243328055312759041486862581886375590662060437737586712108888518883549084601176562967006878103993470602045533933592069621159846260261809969467755897766697495452795453326541782213722112 ┤                                                                      │
 21875000000000004649291976566335148196886824675264915125234060290707605089718836027141047634551919987756040993287143465683137054358071071980658854256156117379486198211733827959508730014656249754288128 ┤                                                                      │
 18750000000000001557048012751637675873499762624656202314917799211317726879442941964276052894291393181905167638912245627091468395180056277256202045807186434738896838391372529364921673336479212787204096 ┤                                                                      │
 15624999999999998464804048936940203550112700574047489504601538131927848669167047901411058154030866376054294284537347788499799736002041482531745237358216752098307478571011230770334616658302175820120064 ┤                                                                      │
 12499999999999995372560085122242731226725638523438776694285277052537970458891153838546063413770339570203420930162449949908131076824026687807288428909247069457718118750649932175747559980125138853036032 ┤                                                                      │
  9374999999999992280316121307545258903338576472830063883969015973148092248615259775681068673509812764352547575787552111316462417646011893082831620460277386817128758930288633581160503301948101885952000 ┤                                                                      │
  6250000000000006184487927629394944646774124101217425620632522158779756420551788125729989480521053611701746708749795677183337318356029589448913616897939365281178719640722597189174113356354073934168064 ┤                                                                      │
  3125000000000003092243963814697472323387062050608712810316261079389878210275894062864994740260526805850873354374897838591668659178014794724456808448969682640589359820361298594587056678177036967084032 ┤                                                                      │
                                                                                                                                                                                                        0 ┼──────────────────────────────────────────────────────────────────────╯
```



https://www.udemy.com/course/datastructurescncpp/learn/lecture/13319452#overview

Asymptotic Notation Video


| 1 < lg n < n < n lg n < n^2 < n^3 < .... < 2^n < 3^n ... < n^n |

                        | polynomial |     |      exponential    |


1 : push into stack
lg n : AVL tree
n : max item in array
n log n : quick sort
n^2 : matrix, graph
2^n : exponential time complexities

Don't start n from n = 0 or n = 1.
Starting value of n can be any starting value

n 0 --|---- infinity
      |------------



| n^3 |       2^n |
| ---     | ---- |
| 2^3=8     | 2^2=4 |
| 10^3=1000 | 2^10=1024 |
| 11^3=1221 | 2^11=2048 |



f(n) = n   ---> O(n)
f(n) = n^2 ---> O(n^2)

f(n) =  n
       sigma i   ----- 1 + 2 + 3 + .... + n  = ((n(n+1))/2) = O(n^2)
        i=1

| lower bound | omega |
| upper bound | big-oh |
| tight bound | theta |

Useful when you cannot get the exact polynomial for a function.

## Dynamic Programming

Dynamic Programming means tabular programming or Dynamic Planning. This term was
created before coding style programming was a thing.

This is a design technique used to solve a class of problems.

Example: Longest Common Subsequence (LCS)

Important in computation biology like finding commonalities in two DNA strings.

Given two sequences `x[1...m]` and `y[1..n]`, find *a* longest sequence common to
both. "a", not "the" LCS.


```plaintext
x: A B C B D A B  | BDB
y: B D C A B A    | BAB
                  | BDAB
                  | BCAB
                  | BCBA
                  = LCS(x, y)
                   * functional notation but not a function it's a relation.
                   * classic misuse of notation
```

Brute force algorithm for solving this algorithm.
  * check every subsequence of x from 1..m (`x[1..m]`) to see if it's also a subsequence of `y[i..n]`
  * analysis check:
    * Q: How long does it take me to see if it's a subsequence of y?
    * A: The length of y which is `O(n)`.
    * Check = `O(n)`
    * Q: How many subsequences of `x` are there?
    * A: 2^m subsequences of `x`
    * running time: `O(n*2^m)` (exponential time = slow!)

Simplification:

1. Look at length of `LCS(y, y)`.
2. Extend the algorithm to find LCS itself.

Notation: `|s|` denotes length of seq s.


15.1 Dynamic Programming

Dynamic Programming, like the divide and conquer method, solves problems by
combining solutions to subproblems.

Divide and conquer algorithms partition the problem into disjoint subproblems,
solve the subproblems recursively, and then combine their solutions to solve the
original problem.

Is like recursivion but also when the subproblems overlap so we don't have to
recompute the same answer over and over.
We save answers to a table to avoid recompute.
It applies to optimization problems.

* it can have many solutions
* wish to find optimal solution
* "an" optimal solution not "the" solution.

Steps:

1. characterize the structure of an optimal solution
1. recursively define the value of an optimal solution
1. compute the value of "an" optimal solution. (bottom-up)
1. construct optimal solution from computed information.

15.1

Rod-cutting Problem

Where to cut steel rods to make the most revenue?
* cuts are free
* i = 1,2,... to price pi in $ for length i

given a rod of length n inches and a table of prices pi for i = 1,2...n
determine the max revenue rn obtainable by cutting up the rods and selling
pieces if pn for a rod is length n is large enough, no cutting might be
necessary.

Recursive top down approach: exponential time 2^n

```plaintext
CUT-ROD(p, n)
  if n == 0
    return 0
  q = -1
  for i = 1 to n
    q = max(q, p[i] + CUT-ROD(p, n-i))
  return q
```

DP - time-memory trade-off.
* exponential solution might be turned into polynomial solution.

TOP down solution:
```plaintext
MEMOIZED-CUT-ROD(p, n)
  let r[0..n] be a new array
  for i = 0 to n
    r[i] = -1
  return MEMOIZED-CUT-ROD-AUX(p, n, r)

MEMOIZED-CUT-ROD-AUX(p, n, r)
  return r[n] if r[n] >= 0
  return 0 if n == 0

  q = -1
  for i = 1 to n
    q = max(q, p[i] + MEMOIZED-CUT-ROD-AUX(p, n-i, r)
  r[n] = q

  return q
```

BOTTOM up solution:

```plaintext
BOTTOM-UP-CUT-ROD(p, n)
  let r[0..n] be a new array
  r[0] = 0

  for j = 1 to n
    q = -1
    for i = 1 to j
      q = max(q, p[i] + r[j - i])

  r[j] = q
  return r[n]
```

Extended solution that prints max revenue and the # of cuts needed for each
length to produce that revenue.

```plaintext
EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
  let r = [0..n]
  let s = [1..n]
  r[0] = 0
  for j = 1 to n
    q = -1
    for i = 1 to j
      if q < p[i] + r[j-1]
        q = p[i] + r[j-1]
        s[j] = i
    r[j] = q
  return r, s
PRINT-CUT-ROD-SOLUTION(p,n)
  (r, s) = EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
  while n > 0
    print s[n]
    n = n - s[n]
```