educative.io

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

Courses
,
#1

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))

#2

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).

#3

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

1 Like
#4

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)

4 Likes
#5

Right, you got it!

#6

Hi, thanks for your answer. Could you explain more about where we using deque? Do you mean tempList.add() operation? I think tempList.add() and result.add() are the same. Why only tempList.add takes O(N) time while result.add takes O(1)?

Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Subarrays with Product Less than a Target (medium) - Grokking the Coding Interview: Patterns for Coding Questions

#7

Thank you so much I was also confused about this!