From 18618f7bf9ee47c1eb7605d17dbe7156f518067a Mon Sep 17 00:00:00 2001
From: mo khan <mo@mokhan.ca>
Date: Mon, 6 Sep 2021 18:46:59 -0600
Subject: determine when msort is faster than isort

---
 notes.md | 79 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 79 insertions(+)

(limited to 'notes.md')

diff --git a/notes.md b/notes.md
index 2997cf6..f21eb7e 100644
--- a/notes.md
+++ b/notes.md
@@ -80,3 +80,82 @@ 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
+    ```
-- 
cgit v1.2.3