# 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.

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 $64n\lg n$ steps. For which values of $n$ does insertion sort beat merge sort?
\begin{aligned} 8n^2 & < 64n\lg n \\ 2^n & < n^8 \\ n & \le 43. \end{aligned}
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}