For this lesson, whys is the complexity O(n^3)? I understand that sliding window takes O(n) and we have another for loop nested that creates the subarrays. Therefore, shouldn’t total runtime be O(n^2)? The lesson doesn’t explain clearly why O(n^3).
Type your question above this line.
Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/5902703286812672
As we can see that we are using two nested for loops which make time complexity O(n *n). additionally, We are using the array’s inbuilt add(ith index, element) function, which takes O(n) due to shuffling the elements within the array.
// tempList.add(0, arr[i]); // time complexity is O(n)
hence overall time complexity is O(n^3)
Your explanation is incorrect. The solution uses a Queue for item_list and therefore any operation including AppendLeft takes constant runtime. Also it uses a List for result and the append operation takes constant time as well since it adds the element to the end of the list.
You would be correct if the solution used a regular list for item_list but it does not. It uses a queue.
I was referring to the java solution, however since you mention that you used queue, I believe you are referring python solution.
You are correct, since dequeue is used and we are performing append left which takes constant time, however, if you observe closely, we are converting dequeue to list, which would take O(k), and if k → n then O(n) complexity will be required to dequeue n element and append into the new list in worst case.
Yes. The Python solution. To clarify, you’re saying since we are converting deque to list, it’s O(n) operation? Wow, that’s subtle.
If so, then it makes sense it’s O(n^3) total runtime. Thank you.