ANURRZ - How can an O(n^2) algorithm work?

The editorial suggests an algorithm which is of O(n^2). But there are at most 100 test cases too. So how can an O(n^2) algorithm work?

n^2 = 10^6

And there are 100 test cases, so 10^8
computations.

I am a beginner, and I’ve heard that we can not process more than 10^7 computations on codechef.

My rule of thumb is 10^8 per second which those constraints satisfy.

This is just an estimate and depends on the algorithm’s constant factor.

I usually don’t take the number of test cases into account unless this number is quite large (1000+). In this case, I assume not all tests will have the worst case limits.

It’s more important to note that n <= 1000 and n^2 = 1 000 000 is a quite normal bound to solve a problem.

The number is 10^8, not 10^7. I had the same misconception.

We must find out who is telling all the beginners that it is 10^7 :stuck_out_tongue:

1 Like