For loop and complexity in game of life

Question

While trying to optimize the performances of a code in C ( 4 glider guns, one in each corner in game of life ) , I had to choose between two scenarios :

int M = (int) DIM / 2 + 1;
for (int y = 1; y < M; y += TILE_SIZE)
  for (int x = 1; x < M; x += TILE_SIZE)
  {
    change |= do_tile(x, y, TILE_SIZE, TILE_SIZE, omp_get_thread_num());
    change |= do_tile(DIM - x, y, TILE_SIZE, TILE_SIZE, omp_get_thread_num());
    change |= do_tile(x, DIM - y, TILE_SIZE, TILE_SIZE, omp_get_thread_num());
    change |= do_tile(DIM - x, DIM - y, TILE_SIZE, TILE_SIZE, omp_get_thread_num());
  }

and

for (int y = 1; y < DIM - 1; y += TILE_SIZE)
  for (int x = 1; x < DIM - 1; x += TILE_SIZE)
    change |= do_tile(x, y, TILE_SIZE, TILE_SIZE, omp_get_thread_num());

If we think of it in a complexity way we get that both of them have the same time complexity:

(DIM/2) * (DIM/2) * 4 = DIM * DIM

but when I execute them the first one always finishes in less than 600ms while the second one finishes in around 650ms. How is that possible ? Is there any better optimization for this configuration of game of life ?

Answer 1

As Oppen said above, the complexity that I gave is just an estimate ( O(DIM * DIM) ). And since processors are not fond of jumps which are inside the loop, so less iterations mean less time.