You’re confusing complexity with actual size on disk.

Ionut Hulub

1

Not at all. O() notation has nothing to do with “disk” or “memory”.

In order to represent a number N, you need O(log(N)) space to represent its log(N) bits, no matter how it is stored.

Of course, if N is small, then it can fit into one word on your processor, but O() is defined as the limiting behavior of an algorithm, so that’s cheating…