# Why creating subarrays take up to O(n^2) in the worst case

Can anyone explain to me why creating subarrays take O(n^2) in the worst case?
Wouldn’t the code below run O(n) time for each time?
for i in range(right, left-1, -1):
temp_list.appendleft(arr[i]))
result.append(list(temp_list))

The code you have given runs in O(n). However, if you notice, it is inside another for loop:

``````for (int right = 0; right < arr.length; right++){
// code
for (int i = right; i >= left; i--) {
// code
}
}
``````

Therefore, its time complexity is O(n^2).

I agree, but the explanation said the overall time complexity is O(n^3) because the creation of subarray is O(n^2) that make me confuse

I found the reason. Since we are using deque, we need to convert it back in to list before push it into the result. The time complexity for conversion is O(k) where k is the number of element in the deque. In the worst case, it can be N, so that why creating a subarray is taking O(n^2)

3 Likes

Right, you got it!