title: For loop and complexity in game of life
body: <p>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 :</p>
  
  <pre><code>int M = (int) DIM / 2 + 1;
  for (int y = 1; y &lt; M; y += TILE_SIZE)
    for (int x = 1; x &lt; 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());
    }
  </code></pre>
  
  <p>and </p>
  
  <pre><code>for (int y = 1; y &lt; DIM - 1; y += TILE_SIZE)
    for (int x = 1; x &lt; DIM - 1; x += TILE_SIZE)
      change |= do_tile(x, y, TILE_SIZE, TILE_SIZE, omp_get_thread_num());
  </code></pre>
  
  <p>If we think of it in a complexity way we get that both of them have the same time complexity:</p>
  
  <p>(DIM/2) * (DIM/2) * 4 = DIM * DIM</p>
  
  <p>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 ?</p>