How to calculate running time of code?

4,494

For a loop like this,

for (int i = 5; i < N; i++)

one way to count the number of iterations is to make a list of the number of different values of $i$ that will occur; each one results in one iteration of the loop. Those values are $$ 5, 6, 7, 8, \ldots, N - 1. $$ In case you still don't recognize how many numbers are in that list, it's almost the same as the list we get for for (int i = 0; i < N; i++), which is $$ 0, 1, 2, 3, 4, 5, 6, \ldots, N - 1. $$ The difference is that when we start at $i=5$, we skip the first five numbers in the longer list. Those iterations never occur. So instead of $N$ iterations, we have only $N - 5$ iterations.

Now for this more complicated example:

for (int i = 0; i < N; i++)
    for (int j = i+1; j < N; j++)
        for (int k = i+1; k < N; k++)
            for (int h = k+1; h < N; h++)

In order to get some clue about how many iterations of the inner loop might occur, it can help to try some actual numbers. So if $N = 4,$ for example, the outer loop runs four times, with values of $i$ ranging from $0$ to $3.$ Let's see what happens within each of those loops:

  • $i=0$: then $j$ runs from $1$ to $3$ (three values), and so does $k.$ But there are only two values of $h$ ($2$ and $3$) for $k=1,$ one value of $h$ ($h=3$) when $k=2,$ and no values of $h$ at all (the loop never iterates even once) when $k=3,$ because $k+1=N.$ So adding up the numbers of $h$-loops for each $k,$ we get $2+1+0,$ and we get the same again for each value of $j,$ which makes $3\cdot(2+1+0)$ times through the innermost loop when $i=0.$

  • $i=1$: then $j$ and $k$ each take only two values ($2$ and $3$); $h$ takes only one value for $k=2$ and none for $k=3.$ Adding up all the innermost loop iterations, we have $1+0$ innermost iterations for each $j,$ for $2\cdot(1+0)$ innermost loop iterations altogether.

  • $i=2$: the only iterations of the middle two loops are for $j=3$ and $k=3,$ but when we get to the $h$ loop there are no values left to iterate over; the total is $1\cdot(0)$ iterations.

  • $i=3$: no iterations of any of the inner loops.

So adding up over all the times through the outermost loop, we get $3\cdot(2+1+0) + 2\cdot(1+0) + 1\cdot(0).$

What if $N=5?$ We then get more iterations of the inner loop while $i=0.$ If you follow the same reasoning as before, you get $4\cdot(3+2+1+0)$ iterations of the innermost loop, followed by $3\cdot(2+1+0)$ and so forth just like before; the total ends up at $4\cdot(3+2+1+0) + 3\cdot(2+1+0) + 2\cdot(1+0) + 1\cdot(0).$

See a pattern? (The reason I have not yet actually calculated the results of adding or multiplying any of these numbers is that I did not want to lose track of the pattern.) Once we see a pattern, if we can write the sum for any $N$ using a suitable notation, we can work with it algebraically. Extending the pattern to larger values of $N,$ the number of inner loops is

$$ f(N) = \sum_{m=1}^{N-1} \left( m \sum_{h=0}^{m-1} h \right). $$

Now the only thing left is to find a more convenient way to represent the total as a formula in terms of $N.$ We can use the fact that $\Sigma_{x=0}^{m-1} x = \frac{m(m-1)}{2}$ to reduce this sum of multiples of sums to just a sum of terms, each of which is a cubic polynomial. It will be useful to know the formulas for $\Sigma_{x=0}^m x^2$ and $\Sigma_{x=0}^m x^3$ too in order to solve this altogether. In the end, it shouldn't be too surprising if the leading term of the formula for the total number of loops is some constant times $N^4,$ since we do after all have four nested loops each counting up by $1,$ albeit from various starting values.


In case the example $N=4$ as described above is still not clear, here is a time sequence of all the values that the variables $i,$ $j,$ $k,$ and $h$ take on during all the loops for $N=4.$ $$\begin{eqnarray} \quad& i &\qquad & j \qquad & k \qquad & h \quad \\ \hline & 0 && 1 & 1 & 2 \\ & 0 && 1 & 1 & 3 \\ & 0 && 1 & 2 & 3 \\ & 0 && 1 & 3 & \\ & 0 && 2 & 1 & 2 \\ & 0 && 2 & 1 & 3 \\ & 0 && 2 & 2 & 3 \\ & 0 && 2 & 3 & \\ & 0 && 3 & 1 & 2 \\ & 0 && 3 & 1 & 3 \\ & 0 && 3 & 2 & 3 \\ & 0 && 3 & 3 & \\ & 1 && 2 & 2 & 3 \\ & 1 && 2 & 3 & \\ & 1 && 3 & 2 & 3 \\ & 1 && 3 & 3 & \\ & 2 && 3 & 3 & \\ & 3 && & & \\ \end{eqnarray}$$ Each line represents a new set of values that occurred. Blank entries mean there was no value of the variable that was less than $N$ when the variables to the left had the values shown. The inner loop executes only for lines where all the variables have values, which is just the lines where the entry for $h$ is not blank.

For example, consider the first four lines of the table. These show the iterations of the $k$ loop when $i=0$ and $j=1:$ two iterations for $k=1,$ then one for $k=2,$ and none at all for $k=3$ (indicated by the blank in the $h$ column), total $2 + 1 + 0.$ But these four lines occur almost exactly the same way three times; the only difference is the value of $j,$ which is $1,$ $2,$ or $3.$ These three repetitions of the pattern $2 + 1 + 0$ result in the term $3\cdot(2 + 1 + 0)$ to count the inner loop iterations for $i=0.$

Similar tables for $N=5$ or even $N=6$ are relatively easy to draw up if the pattern is not clear enough from this table.

Share:
4,494

Related videos on Youtube

user6607
Author by

user6607

Updated on August 01, 2022

Comments

  • user6607
    user6607 over 1 year

    I'm finding great difficulty calculating runtime with loops. It's easy when there is one loop, especially when the counter is being incremented by one:

    for (int i = 0; i < N; i++)
    

    It is clear that the running time is N. But I don't understand loops that don't iterate N times. For instance:

    for (int i = 5; i < N; i++)
    

    Now I can't tell what the running time is because it will not run N times.

    It get's even more difficult when there are nested loops. This was an example that was given to me on an exercise:

    for (int i = 0; i < N; i++)
        for (int j = i+1; j < N; j++)
            for (int k = i+1; k < N; k++)
                for (int h = k+1; h < N; h++)
    

    I don't even know where to begin calculating the running time. All I can do is say that the outer loop runs N times but I can't go further than that. k being equal to i+1 rather than j+1 confuses me even more.

    How can I understand how to calculate the running time with nested loops better?

  • user6607
    user6607 about 9 years
    When $i=0$, why did you get $3\cdot(2+1+0)$ instead of $2\cdot(2+1+0)$?
  • user6607
    user6607 about 9 years
    And where is the $1$ coming from in the "$1\cdot (0)$ iterations" part?
  • user6607
    user6607 about 9 years
    How would calculate the running time by looking at the chart?
  • David K
    David K about 9 years
    Writing a table such as this doesn't generate a formula, at least not directly; we make examples for specific values of $N$ like this in the hope that we recognize some patterns. Often you have to look at examples for more than one value of $N$ to see enough of the pattern to get a formula from it. But I've added a few words trying to use the table to explain the term $3\cdot(2+1+0)$ that I used earlier.
  • miracle173
    miracle173 about 9 years
    -1 One way to solve the problem is only mentioned in two sentences. It doesn't answer the question becuase it does not show how to calculate the formulas. I don't think that one can derive a 4th degree polynomial by looking at your patterns
  • David K
    David K about 9 years
    @miracle173: The question was "where to begin." This is a way to begin. In the version of the answer you read, I stopped one step short of explicitly writing out the general form of the summation. I've added that step. The steps from the program to that formula, I think, are the ones that are the hardest to grasp. From the formula to the polynomial is relatively straightforward.