Big-O рекурсии

Question

Я видел много вопросов Big-O, но я не мог понять это.

Я практиковал некоторые вопросы интервью, и я столкнулся с тем, где я должен найти, существует ли пифагорейская тройка в целочисленном массиве. Я понял, что есть простой способ O (n^3) решить его, но я хотел найти более быстрый способ.

Мой вопрос: есть ли код ниже O (n^2) или O (n^3)? Я запутался, потому что, хотя у меня всего 2 петли, мне нужно пройти n раз n^2 в моем худшем случае, что будет O (n^3).

public boolean findTriple(int[] array) { 
return findT(0, array); 
} 

public boolean findT(int start, array) { 
if(start == array.length-1) { 
    return false; 
} 
int first = array[start]; 
for(int i = 0; i < array.length; i++) { 
    for(int j = i+1; j < array.length; j++) { 
     if(first*first == array[i]*array[i] + array[j]*array[j] || 
      array[i]*array[i] == array[j]*array[j] + first*first || 
      array[j]*array[j] == first*first + array[i]*array[i]) { 
      return true; 
     } 
    } 
} 
return findT(start+1, array); 
} 

Answer 1

Каждый раз, когда функция вызывается, вы делаете O(n^2) операций. Вы вызываете свою функцию n раз. Таким образом, полная сложность: O(n^3)