Solutions to other chapters:
Java Methods A & AB:
|
1. | ||
(a) | T | |
(b) | T -- log2n = log10n * log210 |
2. | (a) | O(n2) |
(c) | O(n) |
3. | (c) | O(log n) |
4. | (a) | P |
(c) | E. This task is equivalent to finding the largest clique in a graph. (A graph is a set of nodes with edges connecting some of the nodes; a set of nodes in a graph is called a clique if any two nodes in that set are connected with an edge.) In complexity theory, there is a proof that this is what is called an NP-complete problem: it is equivalent to a whole class of problems for which no polynomial-time algorithms are known and are unlikely to be ever discovered. |
7. | (a) | always |
(b) | sometimes |
10. | (b) | F |
Copyright © 2006 by Skylight Publishing