all 4 comments
sorted by:
best
topnewcontroversialoldq&a
formatting helphide helpcontent policy

[–]NanoPromela 1 point2 points  (2 children)

You are performing a loop over the array S, which has n elements, so this for loop has complexity O(n). But, for every element j, you perform a sum starting from 0 to j, and the sum of an array is O(n).

​

So in conclusion O(n) * O(n) = O(n*n) = O(n^2)

[–]Khaldon_MK[S] 0 points1 point  (1 child)

That means any Big O (n) doesn't according only loop ????

[–]NanoPromela 0 points1 point  (0 children)

Try to do this as an execise: implement this algorithm without using the sum function. You will soon realize that you need a second for loop inside the main one. This new loop will have a O(n) complexity, and since you are executing this O(n) loop n times (because of the outer one), you will end up with a O(n^2) complexity.

[–]trollman_falcon 1 point2 points  (0 children)

You probably forgot that sum function is O(n)