arr = [1, 2, 5, 6, 7]
total = 0
for i in range(len(arr)):
total += sum(arr[i:])
Is the time complexity for the above code is O(n^2) or O(n^3), the confusion because of the slicing of the list arr. So how does slicing arr effects the time complexity?
Slicing a list is O(k) with k being the size of the slice, which in this case rounds up to O(n). However, in this case, the time complexity is still O(n^2), because arr[i:] is additive with sum(), not multiplicative. We can see this if we decompose it into two separate steps:
for i in range(len(arr)): # executes n times
things_to_sum_over = arr[i:] # runs in (k -> n) time
total += sum(things_to_sum_over) # operates over (k -> n) elements
This gives a total n * 2(k -> n), or 2n^2 = O(n^2).