4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Are you assuming that printing each character in the string is 1 operation? Do we add one for the newline printed by println? $\endgroup$ – edA-qa mort-ora-y Aug 2 '12 at 6:17
  • 1
    $\begingroup$ Just as some formatting help, stackexchange sites can do most TeX maths formatting, so you can put your maths between dollar signs ($) and get maths stuff. I'll edit your post to use this so you get an example. $\endgroup$ – Luke Mathieson Aug 2 '12 at 6:20
  • 1
    $\begingroup$ @edA-qamort-ora-y, to get the formula to match the lecture slides, it seems that we have to assume printing each character is 1 operation, but that the newline is ignored. For some reason. Ofcourse it probably should have the newline as an operation too, but whoever wrote it seems to have ignored that. Or I added it up wrong. That's also quite possible. $\endgroup$ – Luke Mathieson Aug 2 '12 at 6:23
  • $\begingroup$ Note that $i=0, \dots, n-2$. Or is $n = \mathtt{input.length()} - 1$? $\endgroup$ – Raphael Aug 2 '12 at 7:40
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you, I see now that the problem was not actually in my understanding. I was expanding out the formula really wrongly. $\endgroup$ – yoonsi Aug 2 '12 at 7:24
  • $\begingroup$ I saw your related question on math.SE, so between these two, hopefully it all makes sense :). $\endgroup$ – Luke Mathieson Aug 2 '12 at 7:35
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The final result is much nicer if we choose $n=\mathtt{length}$: $\frac{(n-1)n(n+1)}{6}$. $\endgroup$ – Raphael Aug 2 '12 at 7:48
  • $\begingroup$ Thank you for that, but admittedly the sum notation you used went way over my head. Do you think however you could explain where that final formula came from? T(n) = n^3... etc. $\endgroup$ – yoonsi Aug 2 '12 at 8:01
  • $\begingroup$ @yoonsi: I tried to write it down as small-stepped as necessary; there is nothing there but a) using distributive law to pull $i$ (not dependent on $j$) out of the sum, b) rewrite the inner sum into a difference of two sums starting at $1$, c) Gauss' formula. I'll edit in the major steps for the final result. $\endgroup$ – Raphael Aug 2 '12 at 8:05
  • $\begingroup$ @yoonsi: If you want to get into algorithm analysis (either for fun or to pass an exam), you better get used to sum manipulation (among other things). The TCS Cheat Sheet for identities and Concrete Mathematics for a more complete introduction and lots of exercises can be helpful resources. Beyond that, it's exercise. $\endgroup$ – Raphael Aug 2 '12 at 8:27
  • $\begingroup$ Thanks for those resources! Yes, I know I'm far behind. At the school I'm at, this is the first paper that deals with algorithms on this mathematical level and I don't come from a maths background, but I'm trying. If you know of any other good resources, please let me know. I want to get better at this. I will definitely start exercising! $\endgroup$ – yoonsi Aug 2 '12 at 8:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.