StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POHow can I estimate time complexity from a table of values?
text
Body
copied!<p>I know that my naive matrix multiplication algorithm has a time complexity of O(N^3)... But how can I prove that through my table of values? Size is the row or column length of the matrix. So square that for the full matrix size.</p> <ul> <li><p>Size = 100 Mat. Mult. Elapsed Time: 0.0199 seconds.</p> <p>Size = 200 Mat. Mult. Elapsed Time: 0.0443 seconds.</p> <p>Size = 300 Mat. Mult. Elapsed Time: 0.0984 seconds.</p> <p>Size = 400 Mat. Mult. Elapsed Time: 0.2704 seconds.</p> <p>Size = 800 Mat. Mult. Elapsed Time: 6.393 seconds.</p></li> </ul> <p>This is like looking at a table of values and estimating the graph of the function... There has to be some relationship between these numbers, and N^3. How do I make sense of it though?</p> <p>I have provided my algorithm below. I already know it is O(N^3) by counting the loops. How can I relate that to my table of values above though?</p> <pre><code> /** * This function multiplies two matrices and returns the product matrix. * * @param mat1 * The first multiplier matrix. * @param mat2 * The second multiplicand matrix. * @return The product matrix. */ private static double[][] MatMult(double[][] mat1, double[][] mat2) { int m1RowLimit = mat1.length, m2ColumnLimit = mat2[0].length, innerLimit = mat1[0].length; if ((mat1[0].length != mat2.length)) return null; int m1Row = 0, m1Column = 0, m2Row = 0, m2Column = 0; double[][] mat3 = new double[m1RowLimit][m2ColumnLimit]; while (m1Row < m1RowLimit) { m2Column = 0; while (m2Column < m2ColumnLimit) { double value = 0; m1Column = 0; m2Row = 0; while (m1Column < innerLimit) { value += mat1[m1Row][m1Column] * mat2[m2Row][m2Column]; m1Column++; m2Row++; } mat3[m1Row][m2Column] = value; m2Column++; } m1Row++; } return mat3; } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload