is this algorithm O(n^2)?

Question

I have been set a challenge and have been told to solve it in O(n^3) because apparently it is impossible in O(n^2), O(n^2) was the original task but it was changed. The challenge is to write an algorithm that goes through each row of an n*n matrix and then print the whole matrix as a sorted array. Each row of the matrix is already sorted.

Here's what I have and I think it is O(n^2) but am still learning big-O properly so wanted some confirmation if I've done it. It uses an insertion sort utility method to sort the array. Thanks

public int[] mergeMatrix(int[][] matrix) {
    int length = matrix.length;
    int [] sortedMatrixArray = new int[length * length];
    int loop = 1;
    for (int[] i : matrix) {
        for (int j = 0; j < length; j++) {
            switch (loop) {
                case 1:
                    sortedMatrixArray[j] = i[j];
                    break;
                case 2:
                    sortedMatrixArray[j + 3] = i[j];
                    break;
                case 3:
                    sortedMatrixArray[j + 6] = i[j];
                    break;
            }
        }
        loop++;
    }
    insertionSort(sortedMatrixArray);
    return sortedMatrixArray;
}

private void insertionSort(int[] array) {
    for (int firstUnsortedIndex = 0; firstUnsortedIndex < array.length; firstUnsortedIndex++) {
        int newElement = array[firstUnsortedIndex];
        int i;
        for (i = firstUnsortedIndex; i > 0 && array[i-1] > newElement; i--) {
            array[i] = array[i-1];
        }
        array[i] = newElement;
    }
}

EDIT:

public int[] mergeMatrix(int[][] matrix) {
    int length = matrix.length;
    int [] sortedMatrixArray = new int[length * length];
    int loop = 0;
    for (int[] i : matrix) {
        for (int j = 0; j < length; j++) {
            if (loop == 0) {
                sortedMatrixArray[j] = i[j];
            }
            sortedMatrixArray[j + (length*loop)] = i[j];
        }
        loop++;
    }
    insertionSort(sortedMatrixArray);
    return sortedMatrixArray;
}

Answer 1

If n is size of matrix, then matrix have n^2 elements.

YourinsertionSort take n^2 element as input. It works O(k^2) (where k is sze of input), so totally you have O(n^2^2) which is O(n^4).

To make it O(n^3) you can do following

public class App {
    public static void main(String[] args) {
        int[] result = sort(new int[][]{{1, 4, 7}, {2, 5, 8}, {3, 6, 9}});

        System.out.println("result = " + Arrays.toString(result));
    }

    static int[] sort(int[][] matrix) {
        int total = 0;
        for (int i = 0; i < matrix.length; i++) {
            total += matrix[i].length;
        }

        // indexes variable store current position for each row.
        int[] indexes = new int[matrix.length];
        int[] result = new int[total];
        for (int i = 0; i < total; i++) {
            int minIndex = 0;
            int minValue = Integer.MAX_VALUE;
            // this loop search for row with minimal current position.
            for (int j = 0; j < matrix.length; j++) {
                //Ignore row which are exhausted
                if (indexes[j] >= matrix[j].length) {
                    continue;
                }
                if (matrix[j][indexes[j]] <= minValue) {
                    minIndex = j;
                    minValue = matrix[j][indexes[j]];
                }
            }
            result[i] = matrix[minIndex][indexes[minIndex]];
            indexes[minIndex]++;
        }

        return result;
    }
}

This algorithm can be improved from O(n^3) to O(n^2*log(n)) using some advanced data structure which allow to find row with minimal current element faster (some sort of tree).

Answer 2

You're right, it is O(n^2). Your insertionSort is also O(n^2) but since you're calling it after your first 2 for loops are completed, your run time is O(n^2)+O(n^2)=O(n^2)