1
$\begingroup$

Suppose we need to find a tight asymptotic bound on the worst case run time of the following program

t = 0;
for i = 0 to n-1 do
  for j = i+1 to n-1 do
    for k = j+1 to n-1 do
      t++;

I can't for the life of me figure out what the run-time would be. I have a feeling it would have n! in there somewhere, but I can't seem to wrap my head around it. All help is appreciated

$\endgroup$
2
$\begingroup$

I suggest you slightly modify your program, as follows:

int i, j, k, t = 0;
for (i = 0; i <= n - 1; i++)
  for (j = i + 1; j <= n - 1; j++)
    for (k = j + 1; k <= n - 1; k++)
      t++;

Now run this program for various values of $n$ and print the corresponding values of $t$, which is your runtime $T(n)$. Make a guess at the growth rate of $T(n)$ based on this. Try to prove your guess.

Another idea is to try to understand what happens when you have only one loop, then two nested loops, and then all three nested loops. The first case in particular is pretty easy.

$\endgroup$
  • $\begingroup$ 1 loop seems quite simple, it would just run n times. for 2 loops: when i = 0, the loop runs n-1 times, when i = 1, the loop runs n-2 times, etc, so it would be (n-1)!. 3 loops is where I get a little hazy. for j = 1, the 3rd loop would run (n-2)! times, for j = 2, it would run (n-3)! times, etc. So the final worst case run time would be (n-2)! + (n-3)! + (n-4) + .. + 1!. Am I correct? $\endgroup$ – dartagnan Dec 11 '13 at 3:01
  • $\begingroup$ @dartagnan; No, that's not right. Try this: What are the valid configurations for $i$,$j$ and $k$, each time "t++;" runs? How many valid configurations exist? (hint: use combinatorics.) $\endgroup$ – Untitled Dec 11 '13 at 4:55
  • $\begingroup$ You might be mixing up the definition of factorial: the correct one is $n! = (n) \cdot (n-1) \cdot (n-2) \cdots (2) \cdot (1)$. $\endgroup$ – Yuval Filmus Dec 11 '13 at 7:21
1
$\begingroup$

Others have explained how to get the correct answer so I'll explain why your guess of $n!$ is wrong and how you could have worked that out for yourself. I'm not trying to kick you while you're down, just to help you check your intuitions and working in the future, so you can quickly reject wrong answers and home in on something closer to the truth.

First, think about what $n!$ "means". $n!$ is the number of ways of arranging the numbers $1, \dots, n$ in a line. So, if the code fragment is going to take $n!$ steps to run, it has to do something involving as much work as considering all possible permutations of $1, \dots, n$ so, in particular, it must be "thinking about" $n$ different numbers at once. But it doesn't do that – at any one time, it's only keeping track of the three variables i, j and k. It doesn't seem to be doing nearly enough work to get up to $n!$.

Second, consider a simpler version of the program that you can analyze. For example,

t = 0;
for i = 0 to n-1 do
    for j = 0 to n-1 do
        for k = 0 to n-1 do
            t++;

This program definitely does more work than the real program because, here, we consider all possible values for j and k, whereas the real program only considers the values where i < j < k. So, however long the real program takes, it takes less than the simplified version, and the simplified version obviously takes $n^3$ steps.

So now you can think a bit harder about the real program, knowing that if you get an answer that's worse than $n^3$, you must have gone wrong somewhere. Perhaps the next step would be to consider the program

t = 0;
for i = 0 to n-1 do
    for j = i+1 to n-1 do
        for k = 0 to n-1 do
            t++;

which does the j loop properly but still simplifies the k loop. If you can figure out how many steps that program takes, you should then be able to move on to the full version.

$\endgroup$
-1
$\begingroup$

(n-1)(n)(n+1)/6 This is the formula

n(n+1)(n+2)...(n+r-1)/r!

where r is the number of nested loops.

$\endgroup$
  • 1
    $\begingroup$ Don't just type in the results. Give explanations as how you derived it. $\endgroup$ – Untitled Dec 11 '13 at 5:06
  • $\begingroup$ Shouldn't it be ${n \choose r} = \frac{n(n-1)(n-2)...(n-r+1)}{r!}$? By the way, your formula and your result do not match. $\endgroup$ – Untitled Dec 12 '13 at 3:50
  • $\begingroup$ the formella stars from n; in this example n is n-1; where n in formella not the same n in the example ,, to avoid conflict make change the character "n" to "m" in the formella. $\endgroup$ – matrmawi Dec 27 '13 at 1:24

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.