Каковы распространенные методы поиска второго по величине элемента массива и какова временная сложность каждого метода?

Вы можете перебирать массив и отслеживать самый большой и второй по величине элементы:

static int secondLargest(int arr[]) {
    // Input sanity
    if (arr == null || arr.length < 2) {
        throw new IllegalArgumentException("arr must have at least two elements");
    }

    // Initialization
    int max;
    int secondmax;
    if (arr[0] > arr[1]) {
        max = arr[0];
        secondmax = arr[1];
    } else {
        max = arr[1];
        secondmax = arr[0];
   }

   // Go over the rest of the elements
   for (int = 2; i < arr.length; ++i) {
       int elem = arr[i];
       if (elem >= max) {
           secondmax = max;
           max = elem;
       } else if (elem > secondmax) {
           secondmax = elem;
       }
   }

   return secondmax;
}

Это имеет временную сложность O(n) и пространственную сложность O(1), где n — длина массива.

Я оставляю вам другое решение (сложность времени, которую я вам должен):

int max = 0, secondmax = 0;
for( int i = 0; i < n; i++ ) {
    if ( arr[i] > max ) {
          // "secondmax" takes the value contained in "max"
        secondmax = max;
          // "max" takes the value contained in "arr[i]"
        max = arr[i] ;
    }
    else if ( arr[i] > secondmax ) {
          // "secondmax" takes the value contained in "arr[i]"
        secondmax = arr[i];
    }
}

Время -> O(N) Пробел -> O(1)

static int secondLargest(int n,int arr[]){
   int max=arr[0],secondmax=-1;
    if (arr[0]>arr[1]){
        max=arr[0];
        secondmax=arr[1];
    }
    if (arr[0]<arr[1]){
        max=arr[1];
        secondmax=arr[0];
    }
        for(int i=2;i<n;i++){
            if (arr[i]>max){
                secondmax=max;
                max=arr[i];
            }
            else if (arr[i]>secondmax && arr[i]<max){
                secondmax=arr[i];
            }
        }
return secondmax;
    }
}