Time complexity formula of nested loops

Question

I've just begun this stage 2 Compsci paper on algorithms, and stuff like this is not my strong point. I've come across this in my lecture slides.

int length = input.length();
for (int i = 0; i < length - 1; i++) {
    for (int j = i + 1; j < length; j++) {
        System.out.println(input.substring(i,j));
    }
}

"In each iteration, the outer loop executes $\frac{n^{2}-(2i-1)n-i+i^{2}}{2}$ operations from the inner loop for $i = 0, \ldots, n-1$."

Can someone please explain this to me step by step?

I believe the formula above was obtained by using Gauss' formula for adding numbers... I think...

Answer 1

Your intuition is correct, the work is in identifying the things you're adding together.

The first bit is that printing a string of length $m$ takes $m$ operations, so the

System.out.println(input.substring(i,j));

line takes $j-i$ operations. (A side note here is that this code is in Java, unless I'm very much mistaken, and the substring(start, end) method gives the substring beginning at index start and ending at end-1)

So then at each iteration of the outer loop, we're printing a bunch of substrings, starting with a string of length one (just the character at index $i$) and ending with the substring that starts at $i$ and goes to the end of the string input.

To put that a dash more mathematically we're printing strings of length $1, 2, \ldots, n-i$. As the number of operations required to print a string is the same as its length, we're doing $\sum_{k=1}^{n-i}k$ operations. Substituting Gauss's formula for this sum, we get that the number of operations is equal to: $$ \frac{(n-i)(n-i+1)}{2} $$

Then multiplying everything out gives the formula you have in your slides.

Answer 2

Let's work from the outside in.

for (int i = 0; i < length - 1; i++) {

Clearly, this loop is executed $n = \mathtt{length}-1$ times, so we get $\sum_{i=0}^{n-1} \dots$ where $\dots$ stands for the time needed by the loop's body (for iteration $i$). Inside, we have

for (int j = i + 1; j < length; j++) {

which we can translate similarly, obtaining $\sum_{i=0}^{n-1} \sum_{j = i+1}^{n} \dots$. Last but not least, the innermost operation

    System.out.println(input.substring(i,j));

is apparently assumed to take $j-i$ steps (one operation per character).

Putting everything together, we get

$\qquad \begin{align} T(n) &= \sum_{i=0}^{n-1} \sum_{j = i+1}^{n} j - i \\ &= \sum_{i=0}^{n-1} \left[\left(\sum_{j = i+1}^{n} j\right) - (n-i)i\right] \\ &= \sum_{i=0}^{n-1} \left[\left(\sum_{j = 1}^{n} j - \sum_{j = 1}^{i} j\right) - (n-i)i\right] \\ &= \sum_{i=0}^{n-1} \left[\left(\frac{n(n+1)}{2} - \frac{i(i+1)}{2}\right) - (n-i)i\right] \\ &= \sum_{i=0}^{n-1} \left[ \frac{n^2 - (2i - 1)n + i^2 - i}{2}\right] \end{align}$

The term in brackets is what you are looking for.

The whole sum can be evaluated using Gauss' formula and its sibling for summand $i^2$:

$\qquad \begin{align} 2T(n) &= \sum_{i=0}^{n-1} n^2 - \sum_{i=0}^{n-1} 2in + \sum_{i=0}^{n-1} n + \sum_{i=0}^{n-1} i^2 - \sum_{i=0}^{n-1} i \\ &= n^3 - 2n \cdot \sum_{i=0}^{n-1} i + n^2 + \sum_{i=0}^{n-1} i^2 - \sum_{i=0}^{n-1} i \\ &= n^3 - n^2(n-1) + n^2 + \frac{(n-1)n(2n - 1)}{6} - \frac{n(n-1)}{2} \\ &= \frac{12n^2 + 2n^3 - 3n^2 + n - 3n^2 + 3n}{6} \\ &= \frac{2n^3 + 6n^2 + 4n}{6} \end{align}$

which immediately yields

$\qquad \displaystyle T(n) = \frac{n^3 + 3n^2 + 2n}{6}$.