CONCEPT EXERCISES
3.1 Create a method, sample (int n), for which worstTime(n) is O(n) but worstTime(n) is not linear in n. Hint: O(n) indicates that n may be (crudely) viewed as an upper bound, but linear-in-n indicates that n may be (crudely) viewed as both an upper bound and a lower bound. Get the solution of 3.1
3.2 Study the following algorithm:
i = 0;
while (!a [i].equals (element))
i++;
Assume that a is an array of n elements and that there is at least one index k in 0 ... n - 1 such that a
[k].equals (element).
Use Big-O notation to estimate worstTime(n). Use Big-! and Big-" notation to estimate worstTime(n). In plain English, estimate worstTime(n). Get the solution of 3.2
3.3 Study the following method:
/**
* Sorts a specified array of int values into ascending order.
* The worstTime(n) is O(n * n).
*
* @param x – the array to be sorted.
*
*/
public static void selectionSort (int [ ] x)
{
// Make x [0 ... i] sorted and <= x [i + 1] ... x [x.length -1]:
for (int i = 0; i < x.length - 1; i++)
{
int pos = i;
for (int j = i + 1; j < x.length; j++)
if (x [j] < x [pos])
pos = j;
int temp = x [i];
x [i] = x [pos];
x [pos] = temp;
} // for i
} // method selectionSort
a. For the inner for statement, when i = 0, j takes on values from 1 to n - 1, and so there are n - 1
iterations of the inner for statement when i = 0. How many iterations are there when i = 1? When
i = 2?
b. Determine, as a function of n, the total number of iterations of the inner for statement as i takes on
values from 0 to n – 2.
c. Use Big-O notation to estimate worstTime(n). In plain English, estimate worstTime(n)—the choices are constant, logarithmic in n, linear in n, linear-logarithmic in n, quadratic in n and exponential in n. Get the solution of 3.3
3.4 For each of the following functions f, where n = 0, 1, 2, 3, . . ., estimate f using Big-O notation and plain English:
Concept Exercises 129
a. f (n) = (2 + n) * (3 + log(n))
b. f (n) = 11 * log(n) + n/2 − 3452
c. f (n) = 1 + 2 + 3 +· · · + n
d. f (n) = n * (3 + n) − 7 * n
e. f (n) = 7 * n + (n − 1) * log (n − 4)
f. f (n) = log (n2)+ n
g. f (n) =
(n + 1) ∗ log(n + 1) − (n + 1) + 1
n
h. f (n) = n + n/2 + n/4 + n/8 + n/16 + ·· · Get the solution of 3.4
3.5 In the Order Hierarchy in Figure 3.1, we have . . ., O(log n), O(n1/2), . . .. Show that, for integers n >16, log2 n < n1/2. Hint from calculus: Show that for all real numbers x >16, the slope of the function log2 x is less than the slope of the function x1/2. Since log2 (16) == 161/2, we conclude that for all real numbers x >16, log2 x < x1/2. Get the solution of 3.5
3.6 For each of the following code segments, estimate worstTime(n) using Big ! notation or plain English. In each segment, S represents a sequence of statements in which there are no n-dependent loops.
a. for (int i = 0; i * i < n; i++)
S
b. for (int i = 0; Math.sqrt (i) < n; i++)
S
c. int k = 1;
for (int i = 0; i < n; i++)
k *= 2;
for (int i = 0; i < k; i++)
S
Hint: In each case, 2 is part of the answer. Get the solution of 3.6
3.7 .a. Suppose we have a method whose worstTime(n) is linear in n. Estimate the effect of tripling n on run time—the actual time to execute the method in a particular computing environment. That is, estimate runTime(3n) in terms of runTime(n).
b. Suppose we have a method whose worstTime(n) is quadratic in n. Estimate the effect of tripling n on run time—the actual time to execute the method in a particular computing environment. That is, estimate runTime(3n) in terms of runTime(n).
c. Suppose we have a method whose worstTime(n) is constant. Estimate the effect of tripling n on run
time—the actual time to execute the method in a particular computing environment. That is, estimate
runTime(3n) in terms of runTime(n). Get the solution of 3.7
3.8 This exercise proves that the Big-O families do not constitute a strict hierarchy. Consider the function f , defined for all non-negative integers as follows:
n, if n is even;
f (n) =
0, if n is odd
Define a function g on all non-negative integers such that f is not O(g) and g is not O(f ). Get the solution of 3.8
3.9 Show that O(n) = O(n + 7). Hint: use the definition of Big-O. Get the solution of 3.9
3.10 Show that if f (n) is polynomial in n, f (n) cannot be exponential in n. Get the solution of 3.10
3.11 Suppose, for some method, worstTime(n) = nn. Show that the method is an exponential-time method (that is, worstTime(n) is !(xn ) for some real number x >1.0). But show that worstTime(n) is not "(xn )—that is, Big Theta of xn—for any real number x >1.0. Get the solution of 3.11
3.12 This exercise illustrates some anomalies of "(1).
a. Define f (n) to be 0 for all n ≥ 0. Show that f is not "(1), but f is "(0).
b. Define f (n) to be (n + 2)/(n + 1) for all n ≥ 0. Show that f is "(1)—and so can be said to be
“constant”—even though f is not a constant function. Get the solution of 3.12
PROGRAMMING EXERCISES
3.1 In mathematics, the absolute value function returns a non-negative integer for any integer argument. Develop a run method to show that the Java method Math.abs (int a) does not always return a non-negative integer.
Hint: See Programming Exercise 0.1. Get the solution of 3.1
3.2 Assume that r is (a reference to) an object in the Random class. Show that the value of the following expression is not necessarily in the range 0 . . . 99:
Math.abs (r.nextInt()) % 100
Hint: See Programming Exercise 3.1. Get the solution of 3.2
3.3 Develop a run method that initializes a Random object with the default constructor and then determines the elapsed time for the nextInt() method to generate 123456789. Get the solution of 3.3
3.4 Suppose a method specification includes a Big-O estimate for worstTime(n). Explain why it would be impossible to create a unit test to support the Big-O estimate. Get the solution of 3.4
3.5 In the binarySearch method in Section 3.1.2, the average of low and high was calculated by the following expression
(low + high) >> 1
Compare that expression to
low + ((high - low) >> 1)
The two expressions are mathematically equivalent, and the first expression is slightly more efficient, but will return an incorrect result for some values of low and high. Find values of low and high for which the first expression returns an incorrect value for the average of low and high. Hint: The largest possible int value is Integer.MAX_VALUE, approximately 2 billion. Get the solution of 3.5
