What is complexity of this algorithm?

Question

Hi,

i am trying to find out the complexity of this algorithm,

for i = 0; i < X; i++;
for j = 0; j <= i; j++;
for k = 0; k <= j; j++;
// some code here

P.S. If you can point me to a link where i can find such examples, that would just awesome. Thanks.

Answer 1

Do you mean the loops to be nested? I haven't had Algorithm Analysis since 1992, but I'm going to be taking it again sometime in the next year...Hope I get this right.

for (i = 0; i < X; i++) {
  for (j = 0; j <= i; j++) {
    for (k = 0; k <= j; j++) {
      // some code here
    }
  }
}

So the outer i loop executes X times.
The j loop executes i times, so it should execute an AVERAGE of X/2 times.
The k loop executes j times, so it should execute an AVERAGE of X/2/2 = X/4 times.

So (I think) overall complexity is X × X/2 × X/4 = X³/8, so worst case execution is O(X³), and it's probably Ω(X³) also, but I wouldn't stake my life on it.

Answer 2

Think about 3 loops: that is a polynomial of power 3.
However you have constraints: for each i you are looping over j from 0 to i, a factor (1/2) for the X^2 term, and for each k up to j, a factor (1/2)(1/3) for the X^3 term. The linear part is of course proportional to X but for normalization you have a coefficient (1/3) for 1 out of the 3 loops. That gives you the following complexity: c[x] = (1/3) X+(1/2) X^2+(1/6) X^3.
Check that out
X c[X]
3 10
. .
. .
27 3654
etc.