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

Question

Предположим, у нас есть массив w, содержащий n целые числа. Следующим определением и следующим псевдокодом, пожалуйста, скажите, какова временная сложность алгоритма w.r.t. n:

idx[i] = max(j) : 1 <= j < i and w[j] < w[i] 

alg: 
Data: w : array of integers - idx: a pointer to maximum index with the less value. 
Date: w is 1based 

idx[1] = -1 
for i=: 2 to n do 
    j=i-1 
    while w[j] > w[i] and j <> -1 
    { 
    j = idx[j] 
    } 
    idx[i] =j 
end 

Answer 1

У вас есть 2 петли здесь -

1. Первый цикл for loop работает п раз. следовательно, O (n).
2. Второй контур while loop запускается каждый раз от (i-1) + (i-2) + (i-3) + .... + (i-n). он выполняется для (n-1) раз. Скоро).

Комбинирует до O(n^2) algo. Другими операциями являются либо постоянное время, либо время O (n), поэтому пренебрегают.