[jameshart]

Any big O discussion usually breaks down (or at least, changes) if you start taking into account the data size of the operands.

You generally assume for big O purposes, when analyzing sorts for example, that comparisons of elements are constant time, and that swapping elements is constant time.

On an n-bit computer, when dealing with m-bit elements, those assumptions are broadly sound. Comparing two ints doesn’t depend on the ints. Reading or writing the int from memory doesn’t take more or less time either.

But the same algorithm, while it has the same big O relationship to the size of a collection, might have a different constant factor on different CPUs and for different values of m. And you might find that some algorithms that constant factor’s relationship to m has its own big O.

One common place this can bite you is when you try to apply big O analysis that has ‘constant time comparison’ assumption built in to, say, sorting arbitrarily long strings, or inserting into a hash table using arbitrary string keys. Comparing strings or calculating hashes of them is not constant time.

[empath-nirvana]

In a practical sense, how you define big O depends on what you consider to be the inputs to the function. If the runtime doesn't change depending on the size of the inputs that you care about, it's O(1).

Like, you might have a function with 2 inputs, N and M, and the run time is like O(m2^n), but n is fixed at a low number every time you'll run it in practice, so it's really just O(m) for your purposes.

[jameshart]

Right. O(f(n)) is literally only defined for situations where n 1: varies between different runs of the algorithm, and 2: can grow arbitrarily large. Even though in practice ‘arbitrarily large’ is always limited by memory, storage, etc.

Talking about algorithms being O(n) in the number of bits in a value is only reasonable if the number of bits in the value actually varies between runs.