How to measure the polynomial run time?

  Kiến thức lập trình

I’m doing complexity analysis problems. I have to find the polynomials (e.g. 5n^2 + 2n + 2) and big-O of the methods. I’m doing the following one:

public void method(int[][] a, int[][] b) {

    int ra = a.length;
    int ca = a[0].length;
    int cb = b[0].length;
    int[][] c = new int[ra][cb];

    for(int i = 0; i < ra; i++) {
        for(int j = 0; j < cb; j++) {
            for(int k = 0; k < ca; k++) {
                c[i][j] = c[i][j] + a[i][k] * b[k][j];
            }
        }
    }
    return c;
}

I have already counted some of the operations that happen in this method, but I can’t really tell what n would be here. I’m thinking about (ra * ca) + (b.length * cb), but I’m not sure if that could be the input n. If it is, how can I know how many times the outermost loop is running, for example? n/4?

LEAVE A COMMENT