Chapter 1 Flashcards Preview

Algorithm > Chapter 1 > Flashcards

Flashcards in Chapter 1 Deck (3)
Loading flashcards...

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?





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?




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.