Analyzing The Time Complexity

[utkarsh1729]

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?

[ssjgz]

@utkarsh1729

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

No, it states that it is a O(n \times \log \textit{MAX}) algorithm, where \textit{MAX} is the largest element in the array.

This fellow explains why this is so

[utkarsh1729]

Thanks @ssjgz !!!