Skip to content

1.2 Algorithms as a technology


Give an example of an application that requires algorithmic content at the application level, and discuss the function of the algorithms involved.

Drive navigation.


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