CODEWITHSUNDEEP
javascripttime-complexity
peace and love
peace and love

Reputation: 239

How to calculate the time complexity of snippet containing inner loops which may terminate at any point

How to calculate the time complexity of below snippet?

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);
}

Basically this snippet is to calculate for any index i, calculate how many adjacent indexes of heights array are no less than heights[i].

I am a bit confused how to calculate the time complexity in this case. The 2 inner loops may stop at any point.

Thanks

Upvotes: 0

Views: 41

Answers (1)

Josep
Josep

Reputation: 13071

It's quadratic O(n^2).

When evaluating time complexity you should always look at the worst case scenario, unless there is an objective amortization that justifies that worst case to be amortized by all the other cases.

This algorithm is quadratic.

Upvotes: 1

Related Questions