How to calculate Time Complexity of a problem having time limit more than 2 seconds?

Revision en2, by Riyad_Hossain, 2024-04-06 13:29:12

Hello everyone,

Today, I attempted a problem having 6 seconds time limit. This problem has n and q values which need to be taken care of before selecting the expected solution which ultimately will fit into the constraints.

On this problem, as mentioned we need to consider the number of queries in each test case. Please read the full problem for better understanding: Problem Link

Key constraints: The sum of q over all test cases does not exceed 10^5, and the sum of n over all test cases does not exceed 10^5.

So, if I run a nested loop of n inside the loop of q then the time complexity would be O(q*n) that means (10^5)*(10^5) which is 10^10. The problem has a 6 seconds time limit. But this solution gave TLE. My Submission Where do I have to optimize and how can I calculate such a complex scenario where the time limit is more than 1 second and have to consider the number of queries also (basically q value)?

Additional Question: if within 1 second, the 10^8 operation is executable then how many operations can I execute within 6 seconds?

Thanks in advance:)

Tags time complexity, time limit exceeded

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Riyad_Hossain 2024-04-06 13:30:44 12
en2 English Riyad_Hossain 2024-04-06 13:29:12 15 Tiny change: '`10^10`.\nI have a `6 seco' -> '`10^10`.\nThe problem has a `6 seco'
en1 English Riyad_Hossain 2024-04-06 13:23:19 1306 Initial revision (published)