Algorithm Time Complexity

Understanding constraints is very important. It allows you to decide the suitable time complexity that your algorithm needs to run in.

For reference, these are the comparisons of the different time complexities.

Time complexity (10^8 rule)

Standard coding platforms allow a problem to run for around 1s. CPUs can run around 10^8 operations per sec. Let say our constraints look something like this:

• 1 <= arr.length <= 300

Let N = 300. We can plug N into common time complexities to see how many operations they require:

• O(N): 300 operations = Massively over-optimized.
• O(N^2): 90,000 operations = Very safe.
• O(N^3): 27,000,000 (2.7 × 10^7) operations = The Sweet Spot. This fits perfectly within the 10^8 limit.
• O(N^4): 8,100,000,000 (8.1 × 10^9) operations = Time Limit Exceeded (TLE). This will take way too long.
• O(2^N): 2^300 = Astronomically slow (TLE).

Space complexity

Tells us how to handle the storage and memory requirements. Typically there is a 256 MB memory limit. Some things to remember:

• You cannot use the values of the array as direct indices for a frequency array or hash table (e.g., count[arr[i]]++). An array of size 10^8 integers would require roughly 400 MB of RAM, which often exceeds the typical 256 MB memory limit. Instead, use a hashmap.
• An O(N^2) matrix (like a 2D Dynamic Programming table) takes 300 × 300 = 90,000 elements, which is less than 1 MB and totally safe. Even an O(N^3) 3D table (27,000,000 elements ≈ 108 MB) will usually pass, though it’s cutting it close on strict platforms.
• A 32-bit signed integer can hold values up to roughly 2 × 10^9. If your algorithm requires multiplying two elements (10^8 × 10^8 = 10^16) or summing all 300 elements (300 × 10^8 = 3 × 10^10), you will encounter integer overflow. You must use 64-bit integers (long long in C++).