Question

Hi I need help finding the complexity of this algorithm. Could you please answer the complexity line by line not just the final result?

The algorithm is the following one:

int algorithm(int x)
{
    int y = 1;
    while (y <= x-1)
    {
        int z = y*2;
        while (z <= x)
        {
            int w = 1;
            while (w <= z)
            {
                w++;
            }
            z++;
        }
        y++;
    }
}

Any help would be appreciated!

Thanks

Was it helpful?

Solution

int algorithm(int x)
{
    int y = 1;
    while (y <= x-1)    // <<< loop 1
    {
        int z = y*2;
        while (z <= x)  // <<< loop 2
            int w = 1;
            while (w <= z) // <<< loop 3
            {
                w++;
            }
            z++;
        }
        y++;
    }
}

Let's break it down.

Loop 1: you go around (x-1) times: we call this O(x). Easy.

Loop 2: We start Z with 2*y, so 2, 4, 6, ... From there we go until x. Let's add them up:

sum((x-2) + (x-4) + (x-6) + ... + (x - x)) =
x * x / 2 - 2 * (1+2+3+...+x/2) =
x * x / 2 - 2 * (x/2)*(x/2+1) / 2 ~
x * x / 2 - x * x / 4 =
x * x / 4
= O(x^2)

Now the innermost loop: it goes from w = 1 to w = z; so it loops z times. And we know that

z = 2, 4, 6, ... x

So the innermost loop adds something of the order of x (x/2... same thing).

Combining the O(x) of loop 3 with the O(x^2) of loop 2 (which included the effect of the first loop) we conclude the "algorithm" is of order x^3. To verify, we can modify your code:

#include <stdio.h>

int algorithm(int x)
{
    int c = 0;
    int y = 1;
    while (y <= x-1)
    {
        int z = y*2;
        while (z <= x)
        {
            int w = 1;
            while (w <= z)
            {
                c++; // count complexity
                w++;
            }
            z++;
        }
        y++;
    }
    return c;
}

int main(void) {
    int ii;
    for(ii = 200; ii <= 400; ii+=10) {
      printf("%d   %d\n", ii, algorithm(ii));
    }
}

The output is:

200   1338350
210   1549030
220   1780735
230   2034465
240   2311220
250   2612000
260   2937805
270   3289635
280   3668490
290   4075370
300   4511275
310   4977205
320   5474160
330   6003140
340   6565145
350   7161175
360   7792230
370   8459310
380   9163415
390   9905545
400   10686700

Plotting this on a lin-log plot, you get a pretty straight line.

enter image description here

When you take the ratio of algorithm(400) / algorithm(300), you get 2.369. And when you take (400/300)^3, the answer is 2.370. I think that is close enough to be convincing.

OTHER TIPS

Following the formal steps below (I hope you're comfortable with Sigma Notation), you'll be able to obtain the exact order of growth of your algorithm:

enter image description here

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top