There are different models of computation. You can have a model in which integers can be arbitrarily large yet still count as constant memory (for analyzing practical-size algorithms on 64-bit machines, for example); I'm not sure how common those are. I know for example arithmetic is often assumed to be constant time (it indeed varies by input size, even x=y+1, which is clearly O(log(y))).

Also relevant here is the RAM machine model that is often employed, where you can have essentially unlimited memory that can be randomly accessed at fixed time. This again is roughly in line with real practical machines running algorithms that use, and fit within RAM. In reality if you wanted a more physically consistent model eventually your access times must differentiate and increase for increasing memory -- data occupies physical space and must be fetched at increasingly long distances, limited by the speed of light. In principle this means m bits of memory at best can be accessed in O(m^(1/3)) time [1]. Of course, this realism isn't always practically relevant (maybe for datacenter-scale problems, perhaps even larger) and complicates the analysis of algorithms.

[1]: Just for fun, if you want to get really physically accurate, this isn't quite right either I suspect -- that's because with enough data (physical bits) occupying a volume at constant density it will eventually collapse into a black hole, which kinda destroys your computer :). So for planetary-scale computers you eventually need to spread your data across a disk, like a small galaxy (or Discworld, if you prefer :)), so it won't collapse, giving it O(sqrt(m)) access time. Surprise, very large worlds must be flat.

This is related to the BH entropy formula, and the so called Holographic principle, I guess -- the entropy and hence information content of a volume is surprisingly bounded by its area, since a Black Hole's area is proportional to its mass. The weird thing of course is how the universe itself perhaps should collapse to a black hole since it has a lot of stuff in any sufficiently large volume, being young and dynamic it hasn't happened yet. It's alsogiven by its fractal scale, but I guess this digression has grown large enough already :)

(do tell if you want to learn more)

If my integers can be arbitrarily large and count as constant memory, why can't I just reduce everything to a 2-counter machine and solve every problem in constant space (and a lot of time)?

Because the Big O notation as used by engineers is actually about practical problems and not asymptotical behavior.

So integers count as constant memory AND can be considered to be arbitrarily large for the purpose of the current problem. Because having more than 2^64 lines in a file will never happen in practice, and even if it does then 2 integers would do the job for the rest of the observable universe.

Be pragmatic, you are on Hacker News.

Uh, that's what the theory people do, too. We make assumptions about the model, for example, that if our input is of size n, a machine word should be able to store that number (word size θ(log n) bits). Otherwise we'd never get anywhere with asymptotic analysis.

In my experience, practitioners just have a lot of misconceptions about "Big O".

You can, it just makes for a useless result.

With the O() notation the units are some arbitrary computation step or arbitrary unit of memory, which could even mean matrix multiplication of two 1024x1024 matrices of doubles. The whole point of big-O notation is that you don’t care about how fast/expensive it is, but how it scales.

Yes and the memory to store a number scales with the log of the number