Java What is the order of growth (Big-Oh) of the following algorithm(s): 1. disp
ID: 3585038 • Letter: J
Question
Java
What is the order of growth (Big-Oh) of the following algorithm(s):
1. display all integers in an array of integers
2. display all integers in a chain of linked nodes
3. display the nth integer in an array of integers. For example, display the 3rd element in the array, display the 10th element in the array, etc.
4. display the last node in a chain of linked nodes
5. compute the sum of the first n even integers in an array of integers
6. for the following code:
int sum=0;
for(int counter = n; counter > 0; counter = counter-2)
sum = sum + counter;
7. for the following code:
int sum=0;
for(int counter = 1; counter < n; counter = 2 * counter)
sum = sum + counter;
8. for the following code:
for(int pass = 1; pass <= n; pass++) {
for(int index = 0; index < n; index++) {
for(int count = 1; count < 10; count++) {
// code here that is independent of n
}
}
}
9. for the following code:
for(int pass = 1; pass <= n; pass++) {
for(int index = 0; index < n; index++) {
for(int count = 1; count < n; count++) {
// code here that is independent of n
}
}
}
10. of method1:
private static void method1(int[] array, int n) {
for(int index=0; index < n-1; index++) {
int mark = privateMethod1(arrays, index, n-1);
int temp = array[index];
arrays[index] = array[mark];
arary[mark] = temp;
}
}
private static int privateMethod1(int[] array, int first, int last) {
int min = array[first];
int indexOfMin = first;
for(int index = first+1; index <= last; index++) {
if(array[index] < min) {
min = array[index];
indexOfMin = index;
}
}
return indexOfMin;
}
11. of the following task:
You have a book whose words are not sorted in alphabetic order. As a function of the number of words ( n ), what is the complexity of searching for a particular word in the book?
12. of the following task:
You have a dictionary whose words are sorted in alphabetic order. As a function of the number of words ( n ), what is the complexity of searching for a particular word in the dictionary?
Explanation / Answer
1. display all integers in an array of integers
O(n) where n is the length of array
2. display all integers in a chain of linked nodes
O(n) where n is the number of linked nodes
3. display the nth integer in an array of integers. For example, display the 3rd element in the array, display the 10th element in the array, etc.
O(n) nth integer in worst case
4. display the last node in a chain of linked nodes
O(n) where n is the number of linked nodes
5. compute the sum of the first n even integers in an array of integers
O(n)
6. for the following code:
int sum=0;
for(int counter = n; counter > 0; counter = counter-2) ==> Runs Max O(n) times
sum = sum + counter;
Time complexity is O(n)
7. for the following code:
int sum=0;
for(int counter = 1; counter < n; counter = 2 * counter) ==> Runs for log2 n
sum = sum + counter;
Time complexity is O(log2 n)
8. for the following code:
for(int pass = 1; pass <= n; pass++) {====> Runs for n time
for(int index = 0; index < n; index++) {====> Runs for n2 time
for(int count = 1; count < 10; count++) {====> Runs for n3 time
// code here that is independent of n
}
===> Runs for n3 time
}
}
Time complexity is O(n3)
9. for the following code:
for(int pass = 1; pass <= n; pass++) {===> Runs for n time
for(int index = 0; index < n; index++) {===> Runs for n2 time
for(int count = 1; count < n; count++) {===> Runs for n3 time
// code here that is independent of n
===> Runs for n3 time
}
}
}
Time complexity is O(n3)
10. of method1:
private static void method1(int[] array, int n) {
for(int index=0; index < n-1; index++) {==> Runs for n time
int mark = privateMethod1(arrays, index, n-1);==> Runs for at max n time when index is 0
int temp = array[index];
arrays[index] = array[mark];
arary[mark] = temp;
}
}
Overall Time complexity is O(n2)
private static int privateMethod1(int[] array, int first, int last) {
int min = array[first];
int indexOfMin = first;
for(int index = first+1; index <= last; index++) {
if(array[index] < min) {
min = array[index];
indexOfMin = index;
}
}
return indexOfMin;
}
11. of the following task:
You have a book whose words are not sorted in alphabetic order. As a function of the number of words ( n ), what is the complexity of searching for a particular word in the book?
Not sorted means Searching will take O(n) time in worst case if our key is the last book in the list
12. of the following task:
You have a dictionary whose words are sorted in alphabetic order. As a function of the number of words ( n ), what is the complexity of searching for a particular word in the dictionary?
Sorted means Searching will take O(log n) time in worst case as we can apply binary search in Sorted list
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.