I was solving the Minions and Voting (MINVOTE Problem - CodeChef) problem when I came up with the same algorithm that I have given below (copy-pasted from the editorial)
j = 1 to N: i = j+1 to N: if sum(i,j) > A[j]: break ans[i]+=1 i = j-1 to 1: if sum(i,j) > A[j]: break ans[i]+=1
When I was first submitting my code I thought that it would give a TLE whereas I got an AC and it took only 0.12 sec for that. I am surprised because I thought that it is an O(n^2) algorithm but the editorial states that it is an O(n*log n) algorithm. Can anyone please explain me how is it so? And how do we analyze the time complexity of such algorithms where we can’t determine the number of times the code gets executed?