1. Using the big-Oh notation, what is the worst-case time complexity of each of

ID: 3605503 • Letter: 1

Question

1. Using the big-Oh notation, what is the worst-case time complexity of each of the following pieces of code? In every case consider n being the growth rate variable. When there is no variable n in the code, consider that the variable responsible for the growth is n in the big-oh notation.

void test1(int n) {

int m = 10 * n;

while (m > 0) {

System.out.println(n + m);

m--; n = n * 2;

}

} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

void test2(int n) {

int sum = 0;

for (int i = 1; i < n; i ++) {

System.out.println(n);

sum += n;

}

System.out.println(sum);

void test3(int n) {

for (int i = n; i > 1; i--) {

for (int j=1; j < i; j++) {

System.out.println(i+j); }

}

void test4(int n) {

for (int i = 1; i < n; i += 2) {

for (int j = 1; j < n; j *= 2) {

for (int k = 0; k <= 10; k++) {

System.out.println("test");

}

if (arr.length%2==1){

for (int i = 0; i < arr.length; i++) {

System.out.println(arr[i]);

}

} else{

for (int i = 1; i < arr.length; i++) {

arr[i] = arr[i-1];

int j=0;

while (j<=arr.length){

System.out.println(arr[j]);

j=j*2;

}

2. Write a recursive method that sums up all the odd numbers between 1 and n. As an example, if n == 5 the method must return 9, which is the sum 5 + 3 + 1. If n == 6 the method must return 9, as well, because the odd numbers to sum are still 5, 3, and 1. You must use the following method header. public static int recursiveOddSum(int n){

3. You have the following three methods.

public static void recursivePrint1(int r){

if (r==0)

return;

System.out.println(r);

recursivePrint1(r-1);

}

public static void recursivePrint2(int r){

if (r<=1)

return;

recursivePrint2(r/2);

System.out.println(r);

}

public static int recursivePrint3(int r){

System.out.println(r);

if (r<=1)

return 0;

int a= recursivePrint3(r/2);

int b= recursivePrint3(-r/2);

return a+b;

}

(a) What is the terminal output of the method call recursivePrint1(5)?

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

(b) What is the terminal output of the method call recursivePrint2(5)?

4. Suppose you have a doubly linked list of Node objects with char data elements. The Node class is provided below. class Node {

char data;

Node next; // links to the next node

Node prev; // links to the previous node

}

Consider that head is the reference variable that holds the starting non-null node and tail is the last non-null node of the doubly linked list you have. Obviously, both head and tail are instances of the Node class.

(a) Write a recursive method named isPalindrome that checks whether a sequence of characters in a doubly linked list of Node objects forms a palindrome. The method must return true if the sequence forms a palindrome; otherwise, it should return false. As examples, if the linked list contains {A, C, C, A} or {A, C, A} in a sequence then the isPalindrome method should return true. For a sequence, {A, C, C, B}, the isPalindrome method should return false. You must use the following header.

public static boolean isPalindrome(Node head, Node tail) {

(b) What is the time complexity (big-oh) of the isPalindrome method you have written?

5. Write a recursive method that will return the count of vowels in a string. For example, the method should return 5 for an input string application. Assume that string s will not contain uppercase letters.

public static int countVowels(String s){

6. Compute the big-oh time complexity of the following function. You must show the derivation for full credit.

T(n) = T(n/ 3) + c

You might need the following list of formulas to solve this problem.

1+2+3...+(n-1)+n = n(n+1)/2

a^0 + a^1+ a^2 + a^3+....+ a^(n-1)+a^n = a^(n+1)-1/a-1

2^0 + 2^1 + 2^2 + 2^3 + .....+ 2^(n-1) + 2^n = 2^(n+1)-1/2-1

7. Two algorithms, A and B, have the time functions f and g, where f(n) = 10n^2 + 16n + 11 and g(n) = 9n^2 + 22n + 6. Determine which algorithm runs faster. You must show the derivations for full credit. You will need to compute a maximum common point after which one algorithm is faster than the other but before that point the conclusion might not be true.

8. Show divide-and-conquer steps of merge sort on the following array: 15, 8, 13, 11, 7. You must show each step of the algorithm.

Explanation / Answer

1)
a)
void test1(int n) {
int m = 10 * n;
while (m > 0) {
System.out.println(n + m);
m--; n = n * 2;
}
}

Since there is only 1 while loop and it runs 10*n times.So the
Time Complexity=O(n)

b)
void test2(int n) {
int sum = 0;
for (int i = 1; i < n; i ++) {
System.out.println(n);
sum += n;
}
System.out.println(sum);
}
Since there is only 1 for loop and it runs n-1 times and there are 2 statements inside for loop.So the
Time Complexity=2*(n-1)
= O(n)

c)
void test3(int n) {
for (int i = n; i > 1; i--) {
for (int j=1; j < i; j++) {
System.out.println(i+j); }
}
}

There are 2 for loops. 1st loop runs n-1 times and the second for loop depends on the first
for loop.
Time Complexity = (n-1) + (n-2) + (n-2) + .... + 2 + 1
= (n-1)n/2
= O(n2)

d)
void test4(int n) {
for (int i = 1; i < n; i += 2) {
for (int j = 1; j < n; j *= 2) {
for (int k = 0; k <= 10; k++) {
System.out.println("test");
}
}
}
}

3 for loops are there.
1st loop runs n/2 times.
2nd loop runs log2n times
3rd loop runs 10 times.
=> Time Complexity = n/2*log2n * O(1)
= O(n log2n)

Navigate

1. Using the below chemical equation, how many moles of magnesium are needed to

1. Using the body fat data, use matrix calculations to calculate the following:

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

1. Using the big-Oh notation, what is the worst-case time complexity of each of

Question

Explanation / Answer

Related Questions

Navigate