Runtime-complexity of a pseudo code.

Question

Give an analysis of the running time of the following code snippet.
sum = 0
for (i = 0; i < n; i++)
  for (j = 0; j < n; j++)
    if (j < i) {
      for(k = 0; k < j ; k++)
         ++ sum

The outer loop is simple, it can be represented as $\sum_{i}^{n}$. The first inner loop is also $\sum_{j}^{n}$. The inner-most loop however is confusing to me. It only executes when $j < i$, but I'm not sure how to represent that in a mathematical manner so I can give the $\operatorname{O}(n)$. Does the inner loop execute exponentially?

without the $j < i$ it is obvious that it does $\mathcal{O}(n^3)$ loops and with it does $\mathcal{O}(n^3)/2$ loops — reuns, Jan 18 '16 at 03:21

score 2 · Accepted Answer · answered Jan 18 '16 at 04:49

Some of the loops in the second loop are wasted, simplifying your code to

sum = 0 for (i = 0; i < n; i++) for (j = 0; j < i; j++) for(k = 0; k < j ; k++) ++ sum

which does the same thing slightly more efficiently, the mathematical formulation of the problem becomes: How many triplets $(i,j,k)$ are there such that $0\leq k < j < i < n$. This is equivalent to the question of picking three distinct numbers from the set $\{0,1,2,\dots,n-1\}$. The well known answer to that question is: ${n \choose 3} = \frac{n!}{(n-3)!3!} = \frac{n(n-1)(n-2)}{3!} = \frac{n^3-3n^2+2n}{6}$ which as earlier commenters have said is $ O(n^3)$

Runtime-complexity of a pseudo code.

1 Answers1