Counting contiguous subarrays with a negative sum
To get a rough idea, you could consider: how 'deep' does the recursion go, and for each layer, how much work has to be done? See for example the tree in 8.2 Worst-case partitioning, as this is similar to what we have here.


Recurse for every element in the list, so the depth of the recursion tree is of the order n.


For each layer, there is the for loop, which is of the order n, and the array copying, which is also of the order n. So for each layer, there of the order O(n) amount of work to do.



So the algorithm does have complexity O(n^2). Also, is it really necessary to make the copy of the array each time? If your function had a second int start parameter (which is incremented with each recursive call), you could begin the for loop from further down the array with each recursive call, without the need for copies.

This might be a bit crude (and perhaps misleading if you choose the wrong scale), but you can always test it out with some different input sizes to see what happens. Note that with arrays above around 25000 elements I was getting StackOverflowErrors (although rereading the HR task, it was given the array size &lt;= 100). You could do this by generating some random input of different sizes, and timing your function: