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 .
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;
}
Instruction Files
work2.docx
27.9 KB
