CODEWITHSUNDEEP
time-complexityspace-complexity
ZlyVlk
ZlyVlk

Reputation: 29

How to find time and space complexity for this algorithm?

I need to find time and space complexity for this java code for recursive calculation of the determinant of a matrix:

    public int determinant(int[][] m) {
    int n = m.length;
    if(n == 1) {
        return m[0][0];
    } else {
        int det = 0;
        for(int j = 0; j < n; j++) {
            det += Math.pow(-1, j) * m[0][j] * determinant(minor(m, 0, j));
        }
        return det;
    }
}

public int[][] minor(final int[][] m, final int i, final int j) {
    int n = m.length;
    int[][] minor = new int[n - 1][n - 1];
    int r = 0, s = 0;
    for(int k = 0; k < n; k++) {
        int[] row = m[k];
        if(k != i) {
            for(int l = 0; l < row.length; l++) {
                if(l != j) {
                    minor[r][s++] = row[l];
                }
            }
            r++;
            s = 0;
        }
    }
    return minor;
}

Help: Determine the number of operations and memory consumption of the algorithm with respect to n, and after dividing by n^2 you will get the desired result.

I'm confused. I calculate the time complexity as the sum of the input size (n^2) and the number of steps, and the space complexity as the input size. (?) So its O(n^2) but I don't think I'm doing it right. And why should I divide it (help is from the teacher).

Can someone explain to me how to calculate this in this case?

Upvotes: 0

Views: 299

Answers (1)

Gassa
Gassa

Reputation: 8846

Let us see. For an input matrix of size n, denote the time complexity as T(n).

So, for a matrix of size n:

  • if n = 1, we have the answer right away: T(1) = O(1);

  • otherwise, we loop over j for a total of n times, and for each j, we:

    • construct a minor in O(n^2) (the minor function), and then

    • run the function recursively for that minor: this one takes T(n-1) time.

Putting it all together, we have T(1) = O(1) and T(n) = n * (n^2 + T(n-1)).

To understand what is going on, write down what is T(n-1) there:

T(n) = n * (n^2 + T(n-1)) =
= n * (n^2 + (n-1) * ((n-1)^2 + T(n-2)))

And then, do the same for T(n-2):

T(n) = n * (n^2 + T(n-1)) =
= n * (n^2 + (n-1) * ((n-1)^2 + T(n-2))) =
= n * (n^2 + (n-1) * ((n-1)^2 + (n-2) * ((n-2)^2 + T(n-3)))) = ...

Then we write what is T(n-3), and so on. Now, open the brackets:

T(n) = n * (n^2 + (n-1) * ((n-1)^2 + (n-2) * ((n-2)^2 + T(n-3)))) =
= n^3 + n * (n-1) * ((n-1)^2 + (n-2) * ((n-2)^2 + T(n-3)))) =
= n^3 + n * (n-1)^3 + n * (n-1) * (n-2) * ((n-2)^2 + T(n-3)))) =
= n^3 + n * (n-1)^3 + n * (n-1) * (n-2)^3 + n * (n-1) * (n-2) * T(n-3)))) =...

As we can see going further, the highest term among these, in terms of n, will be

T(n) = n * (n-1) * (n-2) * ... * 3 * 2 * 1^3, which is just n! (n-factorial).

The above is about time complexity. To address space complexity, consider how recursion uses memory. Note that it is much different from what happens to the time. The reason is that, at each point of time, we are in some single particular branch of the recursion tree, and at this time other branches don't use the memory they need.

Therefore, unlike with time, we can't just add up the total memory used by all recursive calls. Instead, we have to consider all branches of the recursion tree, and find the one that uses maximum memory. In this particular case, it is just any deepest branch of the recursion.

Denote the memory consumption by M(n) where n is the matrix size.

  • if n = 1, we have the answer right away: M(1) = O(1);

  • otherwise, we loop over j for a total of n times, and for each j, we:

    • construct a minor that takes O(n^2) memory (the minor function), and then

    • run the function recursively for that minor: this one takes M(n-1) memory.

Note that the loop does not accumulate memory used by minors. Instead, when we construct the minor for next j, the minor for previous j is not needed anymore. Thus we have M(n) = n^2 + M(n-1).

Again, writing down what is M(n-1), then M(n-2), and so on gets us to

M(n) = n^2 + (n-1)^2 + (n-2)^2 + ... + 3^2 + 2^2 + 1^2, which is O(n^3) with some constant factor we need not care about.

So, by the above reasoning, the answer is: T(n) = O(n!) and M(n) = O(n^3).
What's the hint about, with dividing by n^2, I don't have a clue, sorry!

Upvotes: 1

Related Questions