Complexity Explorer

✓

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.

Complexity Explorer Santa Fe Institute

Introduction to Computation Theory