Big O Notation

ANCO, as with USACO and all other competitive programming contests, have something known as a “time limit” for every question.

Basically, if your code doesn't finish running in 2 seconds or less, your code will be marked as wrong due to a Time Limit Error (TLE), even if it produces the correct answer! This is because a computer can only do 10^8 operations per second, and thus some correct but extremely slow solutions would time out.

As a result, Big O notation is very important to know for this contest, as it allows you to decipher what type of solution to write for a certain problem.

Every problem will have a different input size denoted as N, and you will see things like N≤ 10⁵, N ≤ 10³, or N≤ 100. That maximum bound of N (e.g. 10⁵, 10³, 100) is actually VERY important; it allows you to know what kind of solution you must write.

Note that a factor of (log N) can be added at the end of any kind of solution for virtually no change in runtime. (So when N ≤ 10⁵, an O(N log N) solution is also feasible, likewise for N≤ 10³, an O(N² log N) solution is feasible, etc.)

If there are two or more input variables for a certain problem (e.g. some problems may have a certain amount of test cases inside each test case denoted as T), a rule of thumb is that when variable values are multiplied together, the result should be less than 10⁸ if you want the code to be fast enough.

For example, if T = 10³ and N = 10³, an O(TN) solution is fast enough (T×N = 10⁶ < 10⁸), but it is not fast enough if T = 10⁵ (T×N = 10⁸ ≥ 10⁸). Similarly, if we were to introduce a third variable K where K = 5, then an O(TNK) solution would be fast enough (T×N×K= 5×10⁶ < 10⁸), but if K = 10³, then it would not be fast enough (T×N×K = 10⁹≥ 10⁸).