CODEWITHSUNDEEP
javaarraysbig-o
PumpkinBreath
PumpkinBreath

Reputation: 915

What is the correct time complexity?

I am writing an algorithm to convert a n*n matrix into a single array.

1 2 3

4 5 6

7 8 9

= [1, 2, 3, 4, 5, 6, 7, 8, 9]

I am confused if what I have done is O(n2) or O(n3):

public int[] mergeMatrix(int[][] matrix) {
    List<Integer> tempList = new ArrayList<>();
    for (int[] array : matrix) {
        for (int i : array) {
            tempList.add(i);
        }
    }
    int totalLength = tempList.size();
    int[] mergedArray = new int[totalLength];
    for (int i = 0; i < tempList.size(); i++) {
        mergedArray[i] = tempList.get(i);
    }
    return mergedArray;
}

Would it be O(n2) because that is the longest worst case of the algorithms processes, or is it O(n3) because O(n) + O(n2) = O(n3)?

Upvotes: 2

Views: 295

Answers (1)

Makoto
Makoto

Reputation: 106390

The runtime complexity of this is O(nm), where n is the number of rows and m is the number of columns in your matrix.

The reason for this:

  • You perform exactly one operation for each element in your matrix total, which is bound by the number of rows and columns you have.

In the context of n = m, then this would be O(n*n) or O(n2), but only then.

The number of loops doesn't really matter here since you could be doing incredibly fancy iteration with it. Be sure to look at the operations you're actually performing in the loop; since they're linear, I would expect the runtime to be a linear runtime times a linear runtime because of the nested nature.

Upvotes: 2

Related Questions