title: How do I get the complexity of bilinear/nearest neighbour interpolation algorithm? (calculate the big O)
body: <p>I want to calculate the big O of the following algorithms for resizing binary images:</p>
  <p><em>Bilinear interpolation:</em></p>
  <pre><code>double scale_x = (double)new_height/(height-1);
          double scale_y = (double)new_width/(width-1);
  
          for (int i = 0; i &lt; new_height; i++)
          {
              int ii = i / scale_x;
              for (int j = 0; j &lt; new_width; j++)
              {
                  int jj = j / scale_y;
                  double v00 = matrix[ii][jj], v01 = matrix[ii][jj + 1],
                          v10 = matrix[ii + 1][jj], v11 = matrix[ii + 1][jj + 1];
                  double fi = i / scale_x - ii, fj = j / scale_y - jj;
                  double temp = (1 - fi) * ((1 - fj) * v00 + fj * v01) +
                      fi * ((1 - fj) * v10 +  fj * v11);
                  if (temp &gt;= 0.5)
                      result[i][j] = 1;
                  else
                      result[i][j] = 0;
              }
          }
  </code></pre>
  <p><em>Nearest neighbour interpolation</em></p>
  <pre><code>double scale_x = (double)height/new_height;
      double scale_y = (double)width/new_width;
  
      for (int i = 0; i &lt; new_height; i++)
      {
          int srcx = floor(i * scale_x);
          for (int j = 0; j &lt; new_width; j++)
          {
              int srcy = floor(j * scale_y);
              result[i][j] = matrix[srcx][srcy];
          }
      }
  </code></pre>
  <p>I assumed that the complexity of both of them is the loop dimensions, i.e O(new_height*new_width). However, the bilinear interpolation surely works much slower than the nearest neighbour. Could you please explain how to correctly compute complexity?</p>