Сложность времени - рекурсивный вызов

Question

Я пытаюсь понять, как вычислить временную сложность алгоритма.

У меня есть этот кусок кода: это весь метод:

public void solve(int i) {
    if(i < 2) {
        return;
    }
    solve(i-1); //recursive call
    int x = v[n-i];
    for(int j = n-i+1; j < n; j++) {
        if(x > v[j]) {
            count++;
        }
    }
    return;
}

Я думаю, что сложность O(n). Я прав?

Спасибо

Answer 1

Сложность должна быть O(N^2) как у вас будет N + (N-1) + (N-2) + 1 = N ( N + 1 ) / 2 итерации в худшем случае.

Answer 2

Сложность O(i^2), n здесь неважно.

Функция запустится i раз (до i<2). каждая итерация будет выполняться i раз (n-(n-i+1)=i-1).

Мы можем назвать это O(N^2) когда N упоминание i,

Заметка! N а также n здесь не то же самое!