Chapter 1

Question 1

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^n steps, while merge sort runs in 64nlg nsteps. For which values of n does insertion sort beat merge sort?

Answer 1

Question 2

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?

Answer 2

Question 3

For each function f(n) and time t in the following table, determine the largest size n of a problem that can be solved in time t, assuming that the algorithm to solve the problem takes f(n) microseconds.

Answer 3