HELP. Please show your work. Determine the order of magnitude for method 1 imple
ID: 667454 • Letter: H
Question
HELP. Please show your work.
Determine the order of magnitude for method 1 implemented in java as below. This method sorts an array of integers in a descending order. 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 void method1(int[] array, int n)
{
for (int index=0; index<n ; index++ )
{
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];
int indexOfMax= first;
for (int index=first+1; index<=last; index++)
if(array[index]>max)
{
max= array[index];
indexOfMax = index;
}
return indexOfMax;
}
Explanation / Answer
The running time of this algorithm in worst case will be O(n).
In this code array will be sorted. In this code method2 is repeatly called in the method1 in a for loop.
The overall running time of the code will be O(n2).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.