Complexity Explorer Santa Fe Institute

Your progress is not being saved! Enroll now or log in to track your progress or submit homework.
Enroll

Introduction to Computation Theory

Lead instructor:

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): $1000000000 \times n^2, 2^n, n^3$
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 $\lim_{n \to \infty} n^3 / (1000000000 \times n^2) = \infty$ and $\lim_{n \to \infty} 2^n / n^3 = \infty$.

 

2) Which algorithm would you rather use for small instances, say $n \leq 10$?

B- For $n = 10$, algorithm 2 takes at most $2^{10} = 1024$ steps, whereas algorithm 3 takes $10^4 = 10,000$ 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 $n=1000000$?

C - Plugging in $n=1000000$, 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 $n^{100}$-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.