Как рассчитать временную сложность фрагмента, содержащего внутренние циклы, которые могут заканчиваться в любой точке

Question

Как рассчитать временную сложность приведенного ниже фрагмента?

let count, barHeight, result = 1 << 31;
for(let i = 0; i < heights.length; i++) {
    count = 1;
    barHeight = heights[i];
    for(let j = i - 1; j >= 0; j--) {
        if (heights[j] >= barHeight) {
            count++;
        } else {
            break;
        }
    }

    for(let k = i+1; k< heights.length; k++) {
        if (heights[k] >= barHeight) {
            count++;
        } else {
            break;
        }
    }

    result = Math.max(result, count*barHeight);
}

По сути, этот фрагмент предназначен для вычисления любого индекса i, подсчитать, сколько смежных индексов массива heights не меньше heights[i].

Я немного запутался, как рассчитать сложность времени в этом случае.2 внутренних цикла могут остановиться в любой точке.

Спасибо

Answer 1

Это квадратичное O(n^2).

При оценке сложности времени вы всегда должны смотреть на наихудший сценарий, если только нет объективной амортизации, которая оправдывает наихудший случай для амортизации во всех остальных случаях.

Этот алгоритм является квадратичным.