Aug 11, 2019 · Aug 11, 2019
diff --git a/book/content/part01/algorithms-analysis.asc b/book/content/part01/algorithms-analysis.asc

 TIP: Asymptotic analysis describes the behavior of functions as their inputs approach to infinity.

 In the previous example, we analyzed `getMin` with an array of size 3; whathappensize is 10 or10k ora million?
 In the previous example, we analyzed `getMin` with an array of size 3; whathappens if thesize is 10,10k, or10 million?
 (((Tables, Intro, Operations of 3n+3)))

 .Operations performed by an algorithm with a time complexity of `3n + 3`

 TIP: Big O only cares about the highest order of the run time function and the worst-case scenario.

 WARNING: Don't drop terms that multiplying other terms. _O(n log n)_ is not equivalent to _O(n)_. However, _O(n + log n)_ is.
 WARNING: Don't drop terms thataremultiplying other terms. _O(n log n)_ is not equivalent to _O(n)_. However, _O(n + log n)_ is.

 There are many common notations like polynomial, _O(n^2^)_ like we saw in the `getMin` example; constant _O(1)_ and many more that we are going to explore in the next chapter.

 Again, time complexity is not a direct measure of how long a program takes to execute but rather how many operations it performs in given the input size. Nevertheless, there’s a relationship between time complexity and clock time as we can see in the following table.
 Again, time complexity is not a direct measure of how long a program takes to execute, but rather how many operations it performs given the input size. Nevertheless, there’s a relationship between time complexity and clock time as we can see in the following table.
 (((Tables, Intro, Input size vs clock time by Big O)))

 // tag::table[]
 |===============================================================
 // end::table[]

 This just an illustration since in different hardware the times will be slightly different.
 Thisisjust an illustration since in different hardware the times will be slightly different.

 NOTE: These times are under the assumption of running on 1 GHz CPU and it can execute on average one instruction in 1 nanosecond (usually takes more time). Also, keep in mind that each line might be translated into dozens of CPU instructions depending on the programming language. Regardless, bad algorithms would perform poorly even on a supercomputer.

diff --git a/book/content/part01/big-o-examples.asc b/book/content/part01/big-o-examples.asc

 ===Big O examples

 There are many kinds of algorithms. Most of them fall into one of the eightof thetime complexities that we are going to explore in this chapter.
 There are many kinds of algorithms. Most of them fall into one of the eight time complexities that we are going to explore in this chapter.

 .Eight Running Time complexity You Should Know
 - Constant time: _O(1)_

 Another more real life example is adding an element to the begining of a <<part02-linear-data-structures#linked-list>>. You can check out the implementation <<part02-linear-data-structures#linked-list-inserting-beginning, here>>.

 As you can see, in both examples (array and linked list) if the input is a collection of 10 elements or 10M it would take the same amount of time to execute. You can't get any moreperformance than this!
 As you can see, in both examples (array and linked list) if the input is a collection of 10 elements or 10M it would take the same amount of time to execute. You can't get any moreperformant than this!

 [[logarithmic]]
 ==== Logarithmic
 include::{codedir}/runtimes/02-binary-search.js[tag=binarySearchRecursive]
 ----

 This binary search implementation is a recursive algorithm, which means that the function `binarySearch` calls itself multiple times until the solution is found. The binary searchsplit the array in half every time.
 This binary search implementation is a recursive algorithm, which means that the function `binarySearch` calls itself multiple times until the solution is found. The binary searchsplits the array in half every time.

 Finding the runtime of recursive algorithms is not very obvious sometimes. It requires some tools like recursion trees or the https://adrianmejia.com/blog/2018/04/24/analysis-of-recursive-algorithms/[Master Theorem]. The `binarySearch` divides the input in half each time. As a rule of thumb, when you have an algorithm that divides the data in half on each call you are most likely in front of a logarithmic runtime: _O(log n)_.

 .Mergesort visualization. Shows the split, sort and merge steps
 image::image11.png[Mergesort visualization,width=500,height=600]

 How do we obtain the running time of the merge sort algorithm? The mergesort divides the array in half each time in the split phase, _log n_, and the merge function join each splits, _n_. The total workwe have*O(n log n)*. There more formal ways to reachtothis runtime like using the https://adrianmejia.com/blog/2018/04/24/analysis-of-recursive-algorithms/[Master Method] and https://www.cs.cornell.edu/courses/cs3110/2012sp/lectures/lec20-master/lec20.html[recursion trees].
 How do we obtain the running time of the merge sort algorithm? The mergesort divides the array in half each time in the split phase, _log n_, and the merge function join each splits, _n_. The total workis*O(n log n)*. Therearemore formal ways to reach this runtime, like using the https://adrianmejia.com/blog/2018/04/24/analysis-of-recursive-algorithms/[Master Method] and https://www.cs.cornell.edu/courses/cs3110/2012sp/lectures/lec20-master/lec20.html[recursion trees].

 [[quadratic]]
 ==== Quadratic
 (((Quadratic)))
 (((Runtime, Quadratic)))
 Running times that are quadratic, O(n^2^), are the ones to watch out for. They usually don’t scale well when they have a large amount of data to process.

 Usually, they have double-nested loops that where each one visits all or most elements in the input. One example of this is a naïve implementation to find duplicate words on an array.
 Usually they have double-nested loops, where each one visits all or most elements in the input. One example of this is a naïve implementation to find duplicate words on an array.

 [[quadratic-example]]
 ===== Finding duplicates in an array (naïve approach)
 include::{codedir}/runtimes/05-has-duplicates-naive.js[tag=hasDuplicates]
 ----

 As you can see, we have two nested loops causing the running time to be quadratic. How muchdifferent is a linear vs. quadratic algorithm?
 As you can see, we have two nested loops causing the running time to be quadratic. How muchdifference is there between a linear vs. quadratic algorithm?

 Let’s say you want to find a duplicated middle name in a phone directory book of a city of ~1 million people. If you use this quadratic solution you would have to wait for ~12 days to get an answer [big]#🐢#; while if you use the <<part01-algorithms-analysis#linear, linear solution>> you will get the answer in seconds! [big]#🚀#

 [[cubic]]
 ==== Cubic
 (((Cubic)))
 (((Runtime, Cubic)))
 Cubic *O(n^3^)* and higher polynomial functions usually involve many nested loops.As an example of a cubic algorithm is a multi-variable equation solver (using brute force):
 Cubic *O(n^3^)* and higher polynomial functions usually involve many nested loops.An example of a cubic algorithm is a multi-variable equation solver (using brute force):

 [[cubic-example]]
 ===== Solving a multi-variable equation
 include::{codedir}/runtimes/06-multi-variable-equation-solver.js[tag=findXYZ]
 ----

 WARNING: This just an example, there are better ways to solve multi-variable equations.
 WARNING: Thisisjust an example, there are better ways to solve multi-variable equations.

 As you can see three nested loops usually translates to O(n^3^). If you have a four variable equation and four nested loops it would be O(n^4^) and so on when we have a runtime in the form of _O(n^c^)_, where _c > 1_, wecanrefer as a *polynomial runtime*.
 As you can see three nested loops usually translates to O(n^3^). If you have a four variable equation and four nested loops it would be O(n^4^) and so on when we have a runtime in the form of _O(n^c^)_, where _c > 1_, we refer to this as a *polynomial runtime*.

 [[exponential]]
 ==== Exponential
 (((Exponential)))
 (((Runtime, Exponential)))
 Exponential runtimes, O(2^n^), means that every time the input grows by one the number of operations doubles. Exponential programs are only usable for a tiny number of elements (<100) otherwise it might not finishon your lifetime.  [big]#💀#
 Exponential runtimes, O(2^n^), means that every time the input grows by one the number of operations doubles. Exponential programs are only usable for a tiny number of elements (<100) otherwise it might not finishin your lifetime.  [big]#💀#

 Let’s do an example.


 As you can see in the `getPermutations` function, the resulting array is the factorial of the word length.

 Factorialstart very slow and then it quickly becomes uncontrollable. A word size of just 11 characters would take a couple of hours in most computers!
 Factorialstarts very slow, and quickly becomes uncontrollable. A word size of just 11 characters would take a couple of hours in most computers!
 [big]*🤯*

 ==== Summary
diff --git a/package-lock.json b/package-lock.json
Original file line number	Diff line number	Diff line change
Expand Up		@@ -115,7 +115,7 @@ When we are comparing algorithms, we don't want to have complex expressions. Wha

		TIP: Asymptotic analysis describes the behavior of functions as their inputs approach to infinity.

		In the previous example, we analyzed `getMin` with an array of size 3; whathappensize is 10 or10k ora million?
		In the previous example, we analyzed `getMin` with an array of size 3; whathappens if thesize is 10,10k, or10 million?
		(((Tables, Intro, Operations of 3n+3)))

		.Operations performed by an algorithm with a time complexity of `3n + 3`
Expand DownExpand Up		@@ -152,11 +152,11 @@ To sum up:

		TIP: Big O only cares about the highest order of the run time function and the worst-case scenario.

		WARNING: Don't drop terms that multiplying other terms. _O(n log n)_ is not equivalent to _O(n)_. However, _O(n + log n)_ is.
		WARNING: Don't drop terms thataremultiplying other terms. _O(n log n)_ is not equivalent to _O(n)_. However, _O(n + log n)_ is.

		There are many common notations like polynomial, _O(n^2^)_ like we saw in the `getMin` example; constant _O(1)_ and many more that we are going to explore in the next chapter.

		Again, time complexity is not a direct measure of how long a program takes to execute but rather how many operations it performs in given the input size. Nevertheless, there’s a relationship between time complexity and clock time as we can see in the following table.
		Again, time complexity is not a direct measure of how long a program takes to execute, but rather how many operations it performs given the input size. Nevertheless, there’s a relationship between time complexity and clock time as we can see in the following table.
		(((Tables, Intro, Input size vs clock time by Big O)))

		// tag::table[]
Expand All		@@ -172,7 +172,7 @@ Again, time complexity is not a direct measure of how long a program takes to ex
		\|===============================================================
		// end::table[]

		This just an illustration since in different hardware the times will be slightly different.
		Thisisjust an illustration since in different hardware the times will be slightly different.

		NOTE: These times are under the assumption of running on 1 GHz CPU and it can execute on average one instruction in 1 nanosecond (usually takes more time). Also, keep in mind that each line might be translated into dozens of CPU instructions depending on the programming language. Regardless, bad algorithms would perform poorly even on a supercomputer.

Expand Down
Original file line number	Diff line number	Diff line change
Expand Up		@@ -5,7 +5,7 @@ endif::[]

		===Big O examples

		There are many kinds of algorithms. Most of them fall into one of the eightof thetime complexities that we are going to explore in this chapter.
		There are many kinds of algorithms. Most of them fall into one of the eight time complexities that we are going to explore in this chapter.

		.Eight Running Time complexity You Should Know
		- Constant time: _O(1)_
Expand DownExpand Up		@@ -47,7 +47,7 @@ include::{codedir}/runtimes/01-is-empty.js[tag=isEmpty]

		Another more real life example is adding an element to the begining of a <<part02-linear-data-structures#linked-list>>. You can check out the implementation <<part02-linear-data-structures#linked-list-inserting-beginning, here>>.

		As you can see, in both examples (array and linked list) if the input is a collection of 10 elements or 10M it would take the same amount of time to execute. You can't get any moreperformance than this!
		As you can see, in both examples (array and linked list) if the input is a collection of 10 elements or 10M it would take the same amount of time to execute. You can't get any moreperformant than this!

		[[logarithmic]]
		==== Logarithmic
Expand All		@@ -68,7 +68,7 @@ The binary search only works for sorted lists. It starts searching for an elemen
		include::{codedir}/runtimes/02-binary-search.js[tag=binarySearchRecursive]
		----

		This binary search implementation is a recursive algorithm, which means that the function `binarySearch` calls itself multiple times until the solution is found. The binary searchsplit the array in half every time.
		This binary search implementation is a recursive algorithm, which means that the function `binarySearch` calls itself multiple times until the solution is found. The binary searchsplits the array in half every time.

		Finding the runtime of recursive algorithms is not very obvious sometimes. It requires some tools like recursion trees or the https://adrianmejia.com/blog/2018/04/24/analysis-of-recursive-algorithms/[Master Theorem]. The `binarySearch` divides the input in half each time. As a rule of thumb, when you have an algorithm that divides the data in half on each call you are most likely in front of a logarithmic runtime: _O(log n)_.

Expand DownExpand Up		@@ -134,15 +134,15 @@ The merge function combines two sorted arrays in ascending order. Let’s say th
		.Mergesort visualization. Shows the split, sort and merge steps
		image::image11.png[Mergesort visualization,width=500,height=600]

		How do we obtain the running time of the merge sort algorithm? The mergesort divides the array in half each time in the split phase, _log n_, and the merge function join each splits, _n_. The total workwe haveO(n log n). There more formal ways to reachtothis runtime like using the https://adrianmejia.com/blog/2018/04/24/analysis-of-recursive-algorithms/[Master Method] and https://www.cs.cornell.edu/courses/cs3110/2012sp/lectures/lec20-master/lec20.html[recursion trees].
		How do we obtain the running time of the merge sort algorithm? The mergesort divides the array in half each time in the split phase, _log n_, and the merge function join each splits, _n_. The total workisO(n log n). Therearemore formal ways to reach this runtime, like using the https://adrianmejia.com/blog/2018/04/24/analysis-of-recursive-algorithms/[Master Method] and https://www.cs.cornell.edu/courses/cs3110/2012sp/lectures/lec20-master/lec20.html[recursion trees].

		[[quadratic]]
		==== Quadratic
		(((Quadratic)))
		(((Runtime, Quadratic)))
		Running times that are quadratic, O(n^2^), are the ones to watch out for. They usually don’t scale well when they have a large amount of data to process.

		Usually, they have double-nested loops that where each one visits all or most elements in the input. One example of this is a naïve implementation to find duplicate words on an array.
		Usually they have double-nested loops, where each one visits all or most elements in the input. One example of this is a naïve implementation to find duplicate words on an array.

		[[quadratic-example]]
		===== Finding duplicates in an array (naïve approach)
Expand All		@@ -157,15 +157,15 @@ If you remember we have solved this problem more efficiently on the <<part01-alg
		include::{codedir}/runtimes/05-has-duplicates-naive.js[tag=hasDuplicates]
		----

		As you can see, we have two nested loops causing the running time to be quadratic. How muchdifferent is a linear vs. quadratic algorithm?
		As you can see, we have two nested loops causing the running time to be quadratic. How muchdifference is there between a linear vs. quadratic algorithm?

		Let’s say you want to find a duplicated middle name in a phone directory book of a city of ~1 million people. If you use this quadratic solution you would have to wait for ~12 days to get an answer [big]#🐢#; while if you use the <<part01-algorithms-analysis#linear, linear solution>> you will get the answer in seconds! [big]#🚀#

		[[cubic]]
		==== Cubic
		(((Cubic)))
		(((Runtime, Cubic)))
		Cubic O(n^3^) and higher polynomial functions usually involve many nested loops.As an example of a cubic algorithm is a multi-variable equation solver (using brute force):
		Cubic O(n^3^) and higher polynomial functions usually involve many nested loops.An example of a cubic algorithm is a multi-variable equation solver (using brute force):

		[[cubic-example]]
		===== Solving a multi-variable equation
Expand All		@@ -184,15 +184,15 @@ A naïve approach to solve this will be the following program:
		include::{codedir}/runtimes/06-multi-variable-equation-solver.js[tag=findXYZ]
		----

		WARNING: This just an example, there are better ways to solve multi-variable equations.
		WARNING: Thisisjust an example, there are better ways to solve multi-variable equations.

		As you can see three nested loops usually translates to O(n^3^). If you have a four variable equation and four nested loops it would be O(n^4^) and so on when we have a runtime in the form of _O(n^c^)_, where _c > 1_, wecanrefer as a polynomial runtime.
		As you can see three nested loops usually translates to O(n^3^). If you have a four variable equation and four nested loops it would be O(n^4^) and so on when we have a runtime in the form of _O(n^c^)_, where _c > 1_, we refer to this as a polynomial runtime.

		[[exponential]]
		==== Exponential
		(((Exponential)))
		(((Runtime, Exponential)))
		Exponential runtimes, O(2^n^), means that every time the input grows by one the number of operations doubles. Exponential programs are only usable for a tiny number of elements (<100) otherwise it might not finishon your lifetime. [big]#💀#
		Exponential runtimes, O(2^n^), means that every time the input grows by one the number of operations doubles. Exponential programs are only usable for a tiny number of elements (<100) otherwise it might not finishin your lifetime. [big]#💀#

		Let’s do an example.

Expand DownExpand Up		@@ -251,7 +251,7 @@ include::{codedir}/runtimes/08-permutations.js[tag=snippet]

		As you can see in the `getPermutations` function, the resulting array is the factorial of the word length.

		Factorialstart very slow and then it quickly becomes uncontrollable. A word size of just 11 characters would take a couple of hours in most computers!
		Factorialstarts very slow, and quickly becomes uncontrollable. A word size of just 11 characters would take a couple of hours in most computers!
		[big]🤯

		==== Summary
Expand Down