What is the time complexity of this code ?

Question

https://code.sololearn.com/cr6a71F367x3/?ref=app

Answer 1

Pramesh I estimate the time complexity to be O(n*log(n)) or less. There are nested loops. The outer loop iterates over the whole array while the inner loop visits linearly decreasing subsets of the array and it may break out early from the inner loop. The lower limit of its time complexity would be O(n).

Answer 2

Thanks Brian 👍

Answer 3

One worst case is a sorted descending array. In that case, the algorithm runs over all subsets size 1 to N-1. That sum, of course, by known formula is (N-1)*N/2 which is an element of O(N²).