Determining Big O(n*n) is relatively straight forward when compared to other forms. Given,

start = 0; end = n; for (i = start; i < end; i++) for (j = start; j < end; j++) doSomething();

It’s clear, for every iteration of the outer loop, the inner loop iterates n times. The outer loop iterates n times as well, so, total number of iterations are n*n. In Big O notation, the runtime complexity may be represented as O(n*n).

But, what about –

```
start = 0;
end = n;
for (i = start; i < end; i++)
for (j = i; j < end; j++)
doSomething();
```

*Note: The inner loop starts iteration at i*

The code above represents a very practical use case, for example, when finding indexOf, substring et al.

When determining the runtime complexity, intuition will suggest O(n*n), which, is correct. But, how do we arrive at that? Because at each iteration, i, of the outer loop, we are iterating n-i times in the inner loop. The number of inner loop iterations are decreasing with each iteration of the outer loop.

Let’s break it down by each iteration –

When,

i = 0, inner loop iterations = n i = 1, inner loop iterations = n - 1 i = 2, inner loop iterations = n - 2 i = 3, inner loop iterations = n - 3 ... i = n - 2, inner loop iterations = n = (n - 2) = 2 i = n - 1, inner loop iterations = n - (n - 1) = 1

Sum total of all iterations –

n + (n - 1) + (n - 2) + (n - 3) .... 2, 1

If we reversed the above, it will look like an **arithmetic series of positive integers up to n**.

1, 2 ... (n - 3) + (n - 2) + (n - 1) + n

Which, as we know is equivalent to –

n(n+1)/2

The above expands to –

(n*n)/2 + (n/2)

In Big O notation (a notation of asymptotic analysis), we drop the lower terms, which, leaves us with –

O(n*n)