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

### computer science

##### Description

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 .

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

## Related Questions in computer science category

##### Disclaimer
The ready solutions purchased from Library are already used solutions. Please do not submit them directly as it may lead to plagiarism. Once paid, the solution file download link will be sent to your provided email. Please either use them for learning purpose or re-write them in your own language. In case if you haven't get the email, do let us know via chat support.