Please help me understand what the number of comparisons used in this method/alg
ID: 3888464 • Letter: P
Question
Please help me understand what the number of comparisons used in this method/algorithm. In my opinion, it is 2+n, because of the if statements in the beginning, and the for loop.
static int secondLargest_Num(int[] arr) {
int first_Largest, second_Largest;
// Check the first two elements of array
// If first element is greater than the second element
if(arr[0] > arr[1]) {
first_Largest = arr[0];
second_Largest = arr[1];
}
// If 2nd element is greater than first element
else {
first_Largest = arr[1];
second_Largest = arr[0];
}
//Check the remaining elements of array
for (int i = 2; i < arr.length; i++) {
if(arr[i] > first_Largest) {
// If element at 'i' position is greater than 'first_Largest'
second_Largest = first_Largest;
first_Largest = arr[i];
} else if (arr[i] < first_Largest && arr[i] > second_Largest) {
// If element at 'i' position is smaller than 'first_Largest' and greater than 'second_Largest'
second_Largest = arr[i];
}
}// end for loop
return second_Largest;
}// end of method
Explanation / Answer
It will be n since
if(arr[0] > arr[1]) {
first_Largest = arr[0];
second_Largest = arr[1];
}
Will be for Once
else {
first_Largest = arr[1];
second_Largest = arr[0];
}
Will be for ONCE
for (int i = 2; i < arr.length; i++) {
if(arr[i] > first_Largest) {
// If element at 'i' position is greater than 'first_Largest'
second_Largest = first_Largest;
first_Largest = arr[i];
} else if (arr[i] < first_Largest && arr[i] > second_Largest) {
// If element at 'i' position is smaller than 'first_Largest' and greater than 'second_Largest'
second_Largest = arr[i];
}
}
Will be for n-2 times.
So in Total n times