Determine the order of magnitude for method 1 implemented in Java below. You do
ID: 3888915 • Letter: D
Question
Determine the order of magnitude for method 1 implemented in Java below. 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. Please keep in mind that method 1 is making a call to method 2. public static void method1(int array[], int n) { for(int index = 0; index < n; index++){ O(n) int mark = method2(array, index, n-1); int temp = array[index]; array[index] = array[mark]; array[mark] = temp; } } public static int method2(int array[], int first, int last) { int max = array[first]; O(1) int indexOfMax = first; O(1) for(int index = first + 1; index <= last; index++){ O(n) if(array[index] > max) { O(n) max = array[index]; O(n) indexOfMax = index; O(1) } } return indexOfMax; } Am I doing this right? Please explain
Explanation / Answer
Please find my answer.
public static void method1(int array[], int n) {
for(int index = 0; index < n; index++) { //O(n)
int mark = method2(array, index, n-1); // O(n-index)
int temp = array[index];
array[index] = array[mark];
array[mark] = temp;
}
}
public static int method2(int array[], int first, int last) {
int max = array[first]; //O(1)
int indexOfMax = first; //O(1)
for(int index = first + 1; index <= last; index++){ // O(last - first)
if(array[index] > max) { //O(1)
max = array[index]; //O(1)
indexOfMax = index; //O(1)
}
}
return indexOfMax;
}
In method1 : for loop is iterating n times and for each value of index, method2 runs : (n-index) times
So, total time: (n-1) + (n-2) + (n-3) + ... + 1
= O(n^2)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.