1.2 Algorithms as a technology

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.

I just created a table showing recently studied sections of this book using the Dataview plugin in Obsidian. It involved sorting algorithms based on the modified time of files and maybe some data structures to filter only the files with a certain tag.

1.2-2

Suppose that for inputs of size $n$ on a particular computer, insertion sort runs in $8n^2$ steps and merge sort runs in $64\ n \lg n$ steps. For which values of $n$ does insertion sort beat merge sort?

$$\begin{aligned} 8n^2 &< 64\ n \lg n \\ n &< 8\log_2 n \\ 2^n &< n^8 \\ 2 \le n &\le 43 \ . \end{aligned}$$

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?

$$\begin{aligned} 100n^2 &< 2^n \\ n &\ge 15 \ . \end{aligned}$$