educative.io

Educative

Why is the time complexity O(n^3) shouldn't it be O(n^2)?

Can someone please help me understand why is the time complexity O(n^3) shouldn’t it be O(n^2)? Why creating subarrays takes O(n^2)?

5 Likes

Because we are adding element at 0 index in templist which is array. So making place at first will need O(n) time.

    tempList.add(0, arr[i]);

But here tempList is LinkedList.
Shouldn’t it be O(1) to add item to first place in LinkedList?

3 Likes

With LinkedList the tc does seem to be N^2, please correct if not so.

2 Likes

@admin with LinkedList the time complexity does seem to be O(n^2).
Please add this point to the solution.

have the same question. Thanks for raising it!