Chapter 1 Exercise 1.2, Introduction to Algorithms, 3rd Edition Thomas H. Cormen

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.

Solution:

Maps are one of the application which requires algorithmic content. One of the basic and widely used algorithm is the shortest path finder between 2 points.

 

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² steps, while merge sort runs in 64n.lg(n) steps. For which values of n does insertion sort beat merge sort?

Solution:

Solving the simple equation:

8n² <64n.lg(n)

n<8.lg(n) (dividing both sides by 8n)

n/8<lg(n) (dividing both sides by 8)

2^n/8<n

2^n/8-n<0

2≤n≤43

Insertion sort is faster for range [2 to 43].

 

1.2-3 What is the smallest value of n such that an algorithm whose running time is 100n² runs faster than an algorithm whose running time is 2ⁿ on the same machine?

Solution:

100n²< 2ⁿ

n	100n2	2n
1	100	2
5	2500	32
10	10000	1024
14	19600	16384
15	22500	32768

For n>14 the 100n² runs faster than 2^n.