Question about time complexity for a certain piece of code:

Revision en2, by karthiksing05, 2023-01-28 00:11:14

hey guys! so i was working on this problem Stick Division on CSES on the USACO Guide. Eventually I got the right answer, but one of my first submissions was this LINK, which I thought ran in O(N^2) time: was very surprised to see that it ran through without being timed out seeing as N was a maximum of 10^5 (ofc 2 out of the 6 test cases passed anyways so still problematic). To summarize: my question is, what's the time complexity of this and if it's higher than O(NlogN), why did it run this way?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English karthiksing05 2023-01-28 00:11:14 7 Tiny change: ' was this (https://' -> ' was this [LINK] (https://'
en1 English karthiksing05 2023-01-27 00:29:21 586 Initial revision (published)