0

What is the time complexity of this code ?

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

6th Dec 2023, 11:37 AM
Pramesh
Pramesh - avatar
3 Respostas
+ 2
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).
6th Dec 2023, 8:31 PM
Brian
Brian - avatar
+ 1
Thanks Brian 👍
7th Dec 2023, 12:15 PM
Pramesh
Pramesh - avatar
+ 1
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²).
7th Dec 2023, 7:16 PM
Gordie
Gordie - avatar