1 Assignment Policies
Collaboration Policy. Homework will be done individually: each student must hand in their own answers. It is acceptable for students to collaborate in understanding the material but not in solving the problems or programming. Use of the Internet is allowed, but should not include searching for existing solutions.
Under absolutely no circumstances code can be exchanged between students. Excerpts of code presented in class can be used.
Assignments from previous offerings of the course must not be re-used. Violations will be penalized appropriately.
Your code must include a comment with your name.
2 Assignment
This assignment asks you to implement a number of methods for a class Complexity. These methods should be implemented using for loops, as seen in class (except for the extra-credit one). In addition, each of these methods should print out the value of an accumulator that counts the number of “operations” performed. The notion of “operation” should be taken loosely; the idea is that if you are requested to implement a method of time complexity O(n), then it should print out values from 1 to n (or close enough). For example, the following code implements a method that has time complexity O(n):
void public method0(int n) { int counter=0; for (i=0; i<n; i++) {
System.out.println("Operation "+counter); counter++;
}
}
2 4 6
The methods you should implement are:
• public static void method1(int n): a method that has time complexity O(n2).
1
• public static void method2(int n): a method that has time complexity O(n3).
• public static void method3(int n): a method that has time complexity O(logn).
• public static void method4(int n): a method that has time complexity O(nlogn).
• public static void method5(int n): a method that has time complexity O(loglogn).
