Рассмотрим 1-индексированный массив натуральных чисел a длины n, где 1 <= a_i <= 10^9, не обязательно упорядочен.
Этот алгоритм вычисляет массив left, где left[i] больше возможный индекс j такой, что a[i] > a[j]. Если a[i] уже является минимумом, то left[i] = 0.
left[0] = 0;
for (int i = 1; i <= n; i++) {
int j = i - 1;
while (j > 0 && a[j] > a[i]) j = left[j];
left[i] = j;
}
Я хочу спросить и понять временную сложность этого алгоритма (и как это доказать).