Time complexity of my algorithm for creating a target array in the given order

Question

What is the time complexity of this algorithm:

public int[] createTargetArray(int[] nums, int[] index) {
    int[] target = new int[nums.length];
    int i = 0, k = 0;
    while (i < index.length) {
        for (k = target.length - 1; k > index[i]; k--)
            target[k] = target[k - 1];
        target[index[i]] = nums[i];
        i++;
    }
    return target;
}

I have provided the input/output and it's explanation below.

Input: nums = [0,1,2,3,4], index = [0,1,2,2,1]
Constraint: nums.length == index.length
Output: [0,4,1,3,2]
Explanation:
nums       index     target
0            0        [0]
1            1        [0,1]
2            2        [0,1,2]
3            2        [0,1,3,2]
4            1        [0,4,1,3,2]

According to my understanding, the while loop takes O(n) time and the inner for loop also takes O(n). Is the time complexity of this solution O(n^2)? Please correct me if I am wrong.

Answer 1

TL;DR More accurately the complexity is O(n * m), O(n^2) if we assume m = n;

According to my understanding, the while loop takes O(n) time and the inner for loop also takes O(n). Is the time complexity of this solution O(n^2)?

First let us re-write your code to:

public int[] createTargetArray(int[] nums, int[] index) {
    int[] target = new int[nums.length];
    for (int i = 0; i < index.length; i++) {
        for (int k = target.length - 1; k > index[i]; k--)
            target[k] = target[k - 1];
        target[index[i]] = nums[i];
    }
    return target;
}

The first loop iterates from i = 0 until index.length and in the worst case scenario (i.e., index[i] is zero) the second loop iteration from k = target.length - 1 until k = 1. So begin n the number of elements in the array index and m the number of elements in the array num. The time complexity of this algorithm is O(n * m).

If one assume that m = n then one can say O(n^2).