How do you reckon Big-O analysis with infinite problem sets?

Question

Let $f : X \to Y$ be a problem, for instance, $f: \Bbb{Z} \to $ a factor.

Given input measure $n = |x|$, then our problem is $O(g)$ if there exists an algorithm running on a standard machine, and an operation counting function $T(n)$, that counts the maximum number of operations on inputs $x \in X$ such that $|x| = n$ such that $T(n)$ is $O(g(n))$.

But how can you reckon this definition with integer multiplication, for example. There isn't a finite memory computer that can hold all integers so how can there be an algorithm that scales this way? Can you describe it as some sort of scaling occuring along an infinite sequence of growing-memory machines?

Answer 1

This is one of those cases where thinking in of turing machines makes things easier compared to thinking in terms of computes as they are actually built.

A turing machine always has potentially infinite memory - it operates by moving along a tape which is assumed to never end. Thus, for a turning machine, the problem your question poses doesn't exists. An algorithmn is $O(g)$ if there's a turing machine and some $C$ such that the turing machine computes the output in at most $Cg(n)$ steps, where $n$ is the size of the input (usually measured in tape cells). How much memory that machine takes is irrelevant, although one can easily see that the amout of tape cells visited is always at most as large as the number of steps the computation takes. This is because:

Turning machines can only move along the tape from one "tape cell" to the next - there's no concept of random accessible memory there.

And that's also the catch. An algorithm might look faster if written in a programming language for a RAM machine than it does for the turning machine, because memory access on a turning machine is $O(n)$ in the worst case. If the machine needs to access one of the $n$ tape cells it has already written to, it can take up to $n$ steps to reach it.

So are RAM machines a better model? Not really! As you say, such a RAM must usually presuppose a maximum memory size. All real-word computers do - a 64-bit architecture can only access $2^64$ individual bytes (or whatever the smallest addressible unit is). And simply scaling up the memory for larger problems is troublesome - we'd also have to scale up the pointer size, thereby using more memory. And also making pointer operations more expensive - if we limit the maximum pointer size to some fixed number of digits, we get away with treating operations on it as $O(1)$, but if that size can grow unbounded, that is no longer true. Operations on pointer are, after all, just arithmetic.

In other words, in the real world, accessing arbitrary amounts of memory is not a O(1) operation.

So you basically have two choices

1. You can works with what I will call true algorithmic complexities, i.e. with runtime bounds which refer to turning machines. To find such a runtime bound for an algorithmn written for a RAM machine, you'll have to be carefull - some operations that look like a single step might not be

2. You can accept the (usually rather slight) imprecision, and treat the atomic operations of RAM machines as single steps. That will generally yield (slightly) lower algorithmic complexities - though in many cases, the difference will vanish in big-O notation anyway.

Answer 2

Let $f: X\to Y$ be a problem, then there is an algorithm that runs in $O(g)$ time $\iff$ there exists a countable sequence of sets $X_0 \subset X_1 \subset \dots = X$ such that for all $i$ and subproblem $f_i: X_i \to Y$ there exists an algorithm that runs in time $T(i, |x|)$ and $\lim_{i \geq k} T(i,|x|) = t(|x|), \forall x \in X_k$ is $O(g(|x|))$.

Proof: $\Rightarrow$, Let $X_0 = X_1 = \dots = X$ be the sequence and so $\lim T(i, |x|) = T(0, |x|)$, which measures all of $X$ so is $O(g)$. $\Leftarrow$, let such a sequence exist. We want to show that $t(|x|)$ effectively measures the running time on all of $X$, in the sense that $t(|x|)|_{X_i} = T(i, |x|)$, but notice that $T(i,|x|)|_{X_{i-1}} = T(i-1,|x|)$ Thus since $\lim T_i = t$ and that $t = \bigcup_{i\in \Bbb{N}} T(i,|x|)$ looking at functions as subsets of $\Bbb{R}^2$ thus $t(|x|)|_{X_i} = \bigcup T(i,|x|)|_{X_i} = \bigcup T(i, |x|) \cup \bigcup_{k \lt i} T(k,|x|)|_{X_i} = T(i, |x|)$, done. Please show that yourself.

Answer 3

As a real-life problem related to this, consider Java's BigInteger class, which needs to multiply arbitrarily large integer representations. The size of the input to the multiplication problem is the length of the representation of the BigInteger instances. Since we might be in the position of evaluating 2k-bit integers, these will not fit into a single long or integer value.

When modeling this, one often assumes either a Turing Machine with some fixed alphabet or a RAM-model with a theoretically unlimited amount of memory available, but still with a limited alphabet and a limited instruction set.

The naive arbitrarily large integer multiplication algorithm requires O($n^2$) time on a RAM model. More sophisticated approaches such as those using the Discrete Fourier Transform or the Katsuboro method can achieve better performance (Google those terms for more info).