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.
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.