You have ignored the much larger space and time cost of constructing the range minimum query tree in the first place. Furthermore, nobody would arbitrarily cut off a problem at “billions” and then consider O(√billions) or O(∜billions) to be “effectively O(1)”: a theoretician would complain that O() by definition measures the limiting behavior as the problem size tends to ∞, an engineer would complain that 65536 or 256 is very a important factor in practice, and both types are better served by leaving O(√n) or O(∜n) as-is instead of trying to hand-wave it away.
Comments
You have ignored the much larger space and time cost of constructing the range minimum query tree in the first place. Furthermore, nobody would arbitrarily cut off a problem at “billions” and then consider O(√billions) or O(∜billions) to be “effectively O(1)”: a theoretician would complain that O() by definition measures the limiting behavior as the problem size tends to ∞, an engineer would complain that 65536 or 256 is very a important factor in practice, and both types are better served by leaving O(√n) or O(∜n) as-is instead of trying to hand-wave it away.