Introduction to Computation Theory
Lead instructor: Josh Grochow
3.1 Resource limitations on algorithms » Quiz Explanation
1) As n gets larger and larger, place these growth rates in order (from smallest to largest):
B - A simple numerical experiment will validate this answer for sufficiently large $n$. More formally, we can take the limits of ratios to find that
2) Which algorithm would you rather use for small instances, say ?
B- For , algorithm 2 takes at most steps, whereas algorithm 3 takes steps, and algorithm 1 takes 10000000000 steps.
3) Same setup as before; which algorithm would you rather use for moderately large instances, say up to ?
C - Plugging in , we find that Algorithm 1 now takes less time than algorithm 3 (the time taken by algorithm 2 for this size of input becomes astronomical).
4) Polynomial-time algorithms are always effective in practice
False - An -time algorithm is rarely ever efficient in practice. We nonetheless like polynomial-time as a definition because (a) it is a robust definition, and (b) historically after a polynomial-time algorithm is shown, even an inefficient one, a truly efficient one is often discovered later. The first discovery of a polynomial-time algorithm for a problem often represents a leap in our understanding of the structure of the problem which can then be further leveraged to get even more efficient algorithms.