Search code examples
javatime-complexitymatrix-multiplication

Matrix Multiplication Algorithm Complexity

I have this Java code for matrix multiplication:

double[][] product(double[][] x, double[][] y) {
    double[][] z = new double[x.length][y[0].length];
    for (int i = 0; i < x.length; i++) {
        for (int j = 0; j < y[0].length; j++) {
            double sum = 0.0;
            for (int k = 0; k < x[0].length; k++) {
                sum += x[i][k]*y[k][j];
            }
            z[i][j] = sum;
        }
    }
    return z;
}

What is the time complexity of this algorithm ? Can I say it is O(n^3) ?

Solution

  • Yes I think it is O(n^3) since you have three loops inside each other