Time complexity formula of nested loops

Question Detail: 

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...

Asked By : yoonsi

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2994

Answered By : Luke Mathieson

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.