How to estimate the number of loop given that the inner loop index always greater than outer loop for Big O complexity estimation?

Question

I have run into a program where there are two nested dependent loops in this manner:

for k=1:K-1
    for ell=k+1:K
        do something
    end
end

How do I calculate the number of total loops this program will run mathematically to estimate the Big O complexity ?

Answer 1

Since the inner loop is in $O(K)$ and it is executed up to $K-1$ times, the big-O cost is quadratic, i.e. $O(K^2)$.

The precise max number of iterations (in the absence of early termination in "do something") is $\displaystyle \sum_{i=1}^{K-1}\ i$, which equals $\displaystyle \frac{K(K-1)}{2}$, confirming the quadratic complexity.