# Analysis of recursive approach for rotating an array of integers

While solving Array rotation on LeetCode, I wrote a recursive algorithm to solve the problem:

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: nums = [-1,-100,3,99], k = 2 Output: [3,99,-1,-100] Explanation: rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100]

Constraints:

1 <= nums.length <= 2*104
-231 <= nums[i] <= 231 – 1
0 <= k <= 105

For further clarification the link to the problem is here.

The solution I came up with is as follows:

```    class Solution {
public void rotate(int[] nums, int k) {

rotateArr(nums,nums.length, k%nums.length, 0);

}

public static void rotateArr(int[] arr, int len, int steps, int current){
if(len <= steps){
return;
}
rotateArr(arr, len - 1, steps, current+1 );
int stepsTaken = 0;
int i = current;
int temp;
while(stepsTaken < steps){
temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
i++;
stepsTaken++;
}
}
}
```

According to my analysis of the solution the function rotateArr() will first divide, by recuring nums.length – k times. After that it start conquering, which will happen in nums.length – k + 1 steps and at each step its performing k operations. Summing up everything we get:

• (nums.length – k) + (nums.length – k + 1) k = nums.length + nums.length k – k^2

Although I have a quadratic term but its a constant, thus I believe my runtime is O(n).
I want to know the following:

• Is my analysis correct ?
• If it’s correct, then why my runtime always falls arround 100 ms on LeetCode ? As opposed to others with 0 ms. Is it because of recursion ?

Utkarsh Tiwari, I think your analysis is not correct. According to my calculation the conquer step will happen for `A.length - k` times and not `A.length - k + 1`.

Let us consider the second input array you mentioned:

```[-1, -100, 3, 99]
```

Here the first call to `rotateArray(A, 4, 2, 0)` takes place in the `main()` method. The second recursive call is this: `rotateArray(A, 3, 2, 1)` and the last one is this: `rotateArray(A, 2, 2, 2)`.

However, in the last recursive call the conquer will not take place since the base condition is satisfied.

```if(length <= steps) return.
```

The function will simply return the last time without performing any significant steps. Hence, all the `k` number of operations will occur only in the first two recursive calls which is according to the expression `A.length - k` or `4-2` in this case.

Hence, the `time complexity` will be `(A.length-k) * k`.

Now, lets look at the constraints you provided:

`1 <= nums.length <= 2 * 10^4`

`-2^31 <= nums[i] <= 2^31 - 1`

`0 <= k <= 10^5`

Here, `k` is not constant. Its possible value even exceeds the maximum value of `nums.length`. The `time complexity` depends both on the value of `A.length` and `k`. It would have been `O(nums.length)` if the possible value of `k` were between 5 to 20. However, with current constraints it can take a value which is more than `A.length`.

Lets notice another subtle detail in your implementation. In the first call to `rotateArray()`, you pass `k % A.length` as one of the parameters. Now the possible value of `k` reduces to:

```0 <= k < A.length
```

If we choose value of k as A.length/2 and put in our time complexity, we get:

```(A.length - A.length/2) * A.length
```

which reduces to `O(A.length^2)` which will be the `worst case complexity`.

I hope I have helped you. Do comment if you face any problems in the solution.