от вопрос уже есть ответ здесь:

может кто-нибудь сказать мне, какова временная сложность этого алгоритма? имейте в виду: второй метод (findMax) - запускается в массиве на основе полученного индекса, что означает, что метод (findMax) не выполняется каждый раз во всем массиве. Я думаю, что временная сложность этого алгоритма O (n), но, возможно, я ошибаюсь.

public class Q2 {


public static int[] replace(int []a)
{
    for(int i = 0; i < a.length; i++ ){
        if(i == a.length-1){
            a[i] = 0; 
       }

        int maxSubArry = findMax(a,i); 

          swap (a, i, maxSubArry);
    }
    return a; 

}


public static int findMax (int[]a, int i)
{
  //  i = i +1; 
    int tmp = 0; 
    for(i = i +1; i<a.length; i++)
    {
        if(a[i] > tmp)
            tmp = a[i];
    }
    return tmp; 
    }


public static void swap(int[]a, int i, int maxSubArry)
{
    int temp = a[i]; 
    a[i] = maxSubArry; 
    a[i+1] = temp; 
}

}