Instructions

Answer the following questions. Submit your answers to questions as a Rich Text Format (.rtf), Word document (.docx), or PDF (.pdf) file.

Part 1 – Big-O 15pts

For the following problems, demonstrate that the functions are in the Big-Oh given using for all . Make sure answers are in positive integer values.

Show that is in . Use C = 8.

Show that is in . Use C = 19.

Show that is in . Pick any integer C > 0.

Part 2 – Big-Omega 15pts

For the following problems, demonstrate that the functions are in the Big-Omega given using

for all . Make sure answers are in positive integer values.

Show that is in . Pick any integer C > 0 (make sure it is sufficiently small).

Show that is in . Use C = 5.

Show that is in . Use C = 157.

Part 3 – Big-Theta 15pts

For the following problem, give and prove the Big-Oh, Big-Omega, and thus the Big-Theta of the function. Provide a graph for both the Big-Oh and Big-Omega inequalities with the constants you chose. You may use wolframalpha.com or any other graphing site to achieve this.

Show that is in .

Explain your analysis.

Part 4 – 12 pts

State the order of magnitude for each of the following mathematical functions in terms of Big-Oh. (Hint: Find the dominant term and drop its coefficient). You do not need to prove anything for these problems.

Part 5 – 18 pts

Assume you have two algorithms, A and B, which perform the same function even though their implementations differ.

Algorithm A has a running time of

Algorithm B has a running time of .

What values of n will make algorithm A more efficient than algorithm B?

What values of n will make algorithm A less efficient than algorithm B?

What values of n will make algorithm A operate with the same time efficiency as algorithm B?

Part 6 – 25 pts

Determine the number of statement executions (precise Big-Oh) for each of the following sample code. You do not need to include the parts inside the construction of the for-loop or conditional of any while-loops as part of your final answer, however, keep in mind it tells you how many times the inner parts will run. Your answers should be in the form of a Big-Oh polynomial (e.g., O(3N2 + 7N + 6)). N is an unknown sized variable and to be assumed to be a positive integer.

Snippet #1

int sum = 0;

for(int i = 0; i < N; i++) {

sum += i;

for(int j = 0; j < N; j++) {

sum += j;

}

}

Snippet #2

int sumi = 0;

int sumj = 0;

for(int i = 0; i < N; i++){

sumi += 1;

sumj += 1;

}

for(int j = 0; j < N; j++) {

sumj += 1;

}

Snippet #3

int sum = 0;

for(int i = N; i >= 0; i--) {

if(i % 2 == 0){

sum += 1;

}

}

Continued on next page…

Snippet #4

for (int i = 0; i < n; i++)

{

sum += i;

}

for (int j = 0; j < n; j++)

{

for (int k = 0; k < n; k++)

{

sum--;

}

}

Snippet #5

for (int i = 0; i < n; i++)

{

for (int j = 0; j < n; j++)

{

for (int k = j; k < j; k++)

{

sum += j;

}

}

}

Bonus Snippet

for(int i = 1; i <= N; i *= 2) {

//Determine the BigO of the number of times the for loop will run.

}

Bonus Points – 10pts

Determine the order of magnitude for method 1 implemented in java as below. This method sorts an array of integers in a descending order. Unlike the previous question, you do not need to count the total number of statement executions to come up with a precise big-Oh; instead, you can use the shortcut rules covered in the lecture for computing the big-Oh. Notice that method 1 includes a statement that calls method 2.

public static int method1(int arr[], int diff) {

int count = 0;

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

int num = arr[i] - diff;

boolean hasNum = method2(arr, i+1, num);

if(hasNum) {

count += 1;

}

}

return count;

}

public static boolean method2(int arr[], int index, int d) {

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

if(arr[index] == d) {

return true;

}

}

return false;

}

work2.docx

27.9 KB

Get Higher Grades Now

Tutors Online