Time Complexity 0.5 sec

What order of time algorithm works for a time limit of 0.5 s?
I am unable to find good reliable documentation for this.

2 Likes

It depends on the constraints.

If N <= 10^6, an O(N log N) solution would easily pass.

(Based on the assumption 10^8 operations take 1 second)

2 Likes

Not necessarily true. The constant for c++ set / map is pretty big and n=10^6 for O(nlogn) won’t easily pass. (You can think of it like each set operation takes 10logn operations).

10 Likes

so only O(N) solution passes for sure,
btw consider complexity for #T .
if T = 10 it’d be 0.05 seconds per test case.

I see…

So only an O(N log N) solution with no constants or coefficients would pass.

For example, nlogn with n=10^6 seems reasonable for binary search / binary indexed tree, both of which have low constants.

1 Like

I am not able to understand this question EXPCH. Can any one explain the example test case ? Is it right to ask clarification of the question when the long challenge is still going on?

Yeah, EXPCH does not really explain the test case very much at all; you have to rely on reading the explanation carefully.

Hopefully you know what is meant by a multiplicative modular inverse. Plenty of articles on that here.