calculateLet T(n) denote the total number of basic computational steps carried out during the invocation
calculate(n)By basic computational steps, we mean comparisons, arithmetic operations, assignments, nested method invocations. Do not count variable declarations. Do not differentiate among other step types when counting. For example, assume that a print statement, an assignment, and an addition, multiplication, or division each count as a single step regardless of the operands.
Find the simplest possible expression for the asymptotic growth rate of the running time T(n) as a function of n. For example, if the total number of basic computational steps T(n) were 5 n2 + 3n, you would give the asymptotic running time as T(n) = Θ(n2) (big Theta of n2). We take T(n) = Θ(f(n)) to mean that the limit limn → ∞ T(n) / f(n) of the quotient of T(n) by f(n) equals some nonzero, finite, constant. (Note: some browsers display Θ as a capital O. To be completely clear, I'm talking about a capital Theta here.) Include an explanation in each case.
a)
static void calculate(int n) {
while (n > 0)
n--;
}
b)
static void calculate(int n) {
for (int i=0; i < 10000; i++)
for (int j=0; j < 10000; j++)
n /= 2;
}
c)
static void calculate(int n) {
for (int i=0; i < n; i++)
for (int j=0; j < n; j++)
n /= 1;
}
d)
static void calculate(int n) {
while (n > 0)
n /= 2;
}
e)
static int calculate(int n) {
int temp;
if (n == 0)
return 1;
else {
temp = calculate(n-1);
return temp*temp*temp;
}
}
f)
static int calculate(int n) {
if (n == 0)
return 1;
else
return calculate(n-1)*calculate(n-1)*calculate(n-1);
}
Note that your answers in this task should be based on an idealized model of computation (e.g., equal times for all step types, and same time for a given basic step independently of the operands). In particular, you should not base your work on any empirical evidence from running an actual program (you'll do that in the next task).
Grading:
a) Define a class named Calculate that includes the methods defined in the preceding task. Rename the methods by adding the letter of the part of the above task that they appear in:
calculateA, calculateB, calculateC, calculateD, calculateE, calculateFProvide code that will allow timing 100 repetitions of the invocation of a given method over a given list of input sizes, n. Do this in the main method for the Calculate class, by filling in the following outline:
public static void main(String[] args) {
String methodsToUse = getString("Enter letters of methods to time (no spaces)");
ArrayList<Integer> sizes = getSizes( getString("Enter list of argument sizes to use (comma- or space-separated)") );
for (int i=0; i<methodsToUse.length(); i++)
timeMethod(methodsToUse.charAt(i), sizes);
}
For example, by entering the letters ABC in response to the first prompt, and the sequence 10,100,1000 in response to the second, the program should first time methodA using n=10, n=100, n=1000, then methodB for the same list of input sizes, and finally methodC for those sizes.
The headers of the methods called from main are as follows:
/**
* measures and prints running times for a given method and a given list of input sizes
* @param c the last character of the method name ('A' through 'Z')
* @param ns the list of desired input sizes
*/
static void timeMethod(char c, ArrayList<Integer> ns)
/**
* makes ArrayList that contains the list of sizes contained in a given String
* @param sizeString a String that contains the desired sizes, separated by spaces or commas
* @return an ArrayList of Integers equal to the sizes specified in sizeString
*/
static ArrayList<Integer> getSizes(String sizeString)
For the actual timing, you may want to define a Timer class like the one that we discussed in class. I also suggest using the standard StringTokenizer class in the implementation of the getSizes method. Refer to the API docs on Oracle's Java site (see CS101 homepage for link).
b) Run the timing program for each of the six methods, over as large a range of n as feasible for a given method. Try powers of 10 first:
Note that some of the methods will become unusably slow, or will crash, for larger values of n. You may need to try smaller values of n in such cases. You should aim to establish the performance level, and the practical limits of n, for each individual method over the largest possible range of n for that particular method.
c) Discuss the results, in particular how they relate to your conclusions in the preceding task (the analytical approach). Discuss any pros or cons of the analytical and empirical approaches based on your experience in this homework assignment.
Grading: