Time & Space Complexity

“10 to the 8th operations per second” is the rule of thumb every competitive programmer learns and the reason so many of them get a surprise verdict. A hash map lookup and an array read are both one operation in Big-O and differ by roughly 3 times in wall clock; the same loop in CPython rather than C++ differs by around 40. The Time and Space Complexity Calculator multiplies those factors in rather than pretending one number covers everything.

Pick an input size, a language, a data structure and a time limit, and each of 9 complexity classes reports an estimated running time and a verdict band. SAFE means under 40% of the limit, RISKY means up to 90%, and TLE means over. Bands rather than a tick and a cross, because the interesting answer is usually the middle one.

Everything is arithmetic in the page. Nothing is compiled, nothing is benchmarked, and no code is uploaded. The estimate is a model, and the model is stated on screen so you can argue with it.

What Each Multiplier Represents

• Languages are scaled against a C++ tight loop at 1. Java is 2.5 for bounds checks and object overhead, PyPy is 6, and CPython is 40 for per-operation bytecode dispatch.
• Structures are scaled against sequential array access at 1. A hash map is 3, an ordered map or segment tree is 9 because each level is a pointer chase into a cache miss, and recursion is 4 for call frames and unpredictable branches.
• Random array access carries the heaviest structure multiplier at 20, and it is the one with no asymptotic penalty at all. That is pure memory latency once the data no longer fits in cache, which is exactly the cost Big-O is blind to.
• The baseline rate is 1 billion cheap operations per second, deliberately higher than the traditional 10 to the 8th, since the multipliers now carry the pessimism that the old constant was hiding.
• Time limits from 1 to 5 seconds cover the usual judge settings, and changing the limit rebands every row at once without recomputing the operation counts.

The Method Behind the Estimate

• Effective time is the raw operation count multiplied by the structure factor, multiplied by the language factor, divided by the baseline rate. Three numbers and a division.
• At N of 100,000, an O(N²) algorithm is 10 billion raw operations, which is 10 seconds in C++ on arrays and 400 in CPython. Both are a fail, but only one is fixable by micro-optimising.
• At N of 1,000,000, O(N log N) is about 20 milliseconds in C++ on arrays. Move that to CPython with an ordered map and the same asymptotic work takes over 7 seconds, which is the gap that decides contests.
• Counts above roughly 10 to the 21st render as ∞ (too large) rather than a meaningless figure, and the exponential and factorial classes cap their exponents at 60 and 20 so the arithmetic stays finite.
• Operation counts are shown in K, M, B, T and P units so that two classes an order of magnitude apart are visibly so.

Accuracy of a Wall-Clock Guess

• Constant factors inside your own code are invisible to this model. A modulo in an inner loop, a division, or an allocation per iteration can each cost more than the structure multiplier being applied.
• Big-O hides its own constants too. Two O(N log N) sorts can differ by 3 times, and the notation cannot tell you which you wrote.
• Judge hardware varies, and so does compiler version and optimisation flag. Treat a RISKY band as genuinely uncertain rather than as a near miss.
• Java carries a JIT warm-up cost that this flat multiplier cannot represent, so short-running Java solutions are penalised more than they deserve and long-running ones less.
• The multipliers are conventional community heuristics, not measurements from a lab. They are right about the ordering and approximate about the size.