Java. Counting operations to produce polynomials. Below are a few different bodi
ID: 3762941 • Letter: J
Question
Java. Counting operations to produce polynomials. Below are a few different bodies of code, analyze each code section and build a polynomial that represents the number of abstract operations the code performs. For the following code segments below, count the operations and produce a corresponding polynomial representation.
1. f(x) =
public static boolean isEmpty() {
return head == null;
}
2. f(x) =
public static int num_occurrences(int n) {
int count = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(i == j) continue;
if(strings[i] == strings[j]) {
count++;
}
}
}
return count;
}
3. f(x) =
public static void c(int n) { //three loops
for(int a = 0; a < n; a++) {
System.out.println( a * a );
}
num_occurrences(n);
}
4. f(x) =
public static boolean isPrime(int n) {
if(int i = 2; i < n; i++) return false;
for (int i = 2; i < n; i++) {
if(n%i == 0) {
return false;
}
}
return true;
}
Explanation / Answer
please note I am assuming all the operations like assignment and comparision is constant
1. f(x) =
public static boolean isEmpty() {
return head == null;
}
f(x)= c(constant)
2. f(x) =
public static int num_occurrences(int n) {
int count = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(i == j) continue;
if(strings[i] == strings[j]) {
count++;
}
}
}
return count;
}
f(x)= x^2+ c because there are 2 loops one inside other for outer loop inner loop fully execute. so total n*n operations will perform and constant for comparision and assignment operations. Where x is input size.
3. f(x) =
public static void c(int n) { //three loops
for(int a = 0; a < n; a++) {
System.out.println( a * a );
}
num_occurrences(n);
}
f(x)= x^2+x+c because first for loop will execute then it will call function in which 2 loops are present one inside other. First loop take n operations and other 2 loops takes n^2 operations.
4. f(x) =
public static boolean isPrime(int n) {
if(int i = 2; i < n; i++) return false;
for (int i = 2; i < n; i++) {
if(n%i == 0) {
return false;
}
}
return true;
}
f(x)= x^2+2x+c because first loop will execute n-1 times and for every iteration inner loop will execute n-1 times. So total (n-1)*(n-1).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.