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.

Drive navigation.

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 $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 \\ 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} $$