Нахождение биг-о сложности.из трех алгоритмов

Question

Я пытаюсь найти временную сложность следующего алгоритма.

Из того, что я вижу, первые два цикла в alg1: n ^ 2 , однако я не уверентогда какое время работы цикла в alg2.

public class algo {




public static int alg1(int[] A, int n) {
    int l = 0;

    for (int i = 0; i <= n-1; i++) {
        for (int j = i+1; j <= n-1 ; j++) {
           if(alg2(A,i,j) && j-i > l) {
               l = j-i+1;
           }
        }
    }

    return l;

}

private static boolean alg2(int[] A,int i, int j) {
    if(i==j) {
        return true;
    }

    for (int k = i; k <= j-1; k++) {
        if(A[k] != A[k+1]) {
            return false;
        }
    }

    return true;
}
}

Answer 1

alg2 - это O (n)

alg1, поскольку внутри него есть alg2, поэтому оно должно быть O (n ^ 2 * n) = O (n ^ 3),Если вы хотите это доказать:

Answer 2

Вы правы, первый Alg1 имеет временную сложность O (n ^ 2).Вторая функция Alg2 имеет временную сложность O (n), потому что производительность алгоритма будет расти линейно пропорционально его входному размеру.У вас есть только один цикл for, и вы нигде не применяете технику D & C в этом коде.