0
$\begingroup$

Suppose that I have a restricted Turing Machine - it has finite tape and takes bounded input. Consider a program that halts on every input (which is at most $k$ bits). The set of inputs is finite, therefore the function describing running time is bounded and hence is $\mathcal O (1)$.

Therefore, when analyzing any algorithm that has been tuned to support some machine requirement (ex. input is 32 bit integer), if it halts, we may say it's $\mathcal O (1)$.

What am I missing here? What are arguments supporting/opposing this point of view?

| cite | improve this question | |
$\endgroup$
2
$\begingroup$

By definition, every algorithm (that always halts) on a finite domain has $O(1)$ running-time: pick $n_0 > \max \{ |x| \mid x \in D\}$ with $D$ the input domain of the algorithm.

However, that fact is utterly uninteresting. Asymptotics are designed to help make statements for "large n", expressed through a limit process; they are simply meaningless if the domain is bounded, or the inputs you see in practise are "small".

As a consequence, if you are concerned with finite domains you'll have to use different mathematical notions, and potentially different machine models.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, but that doesn't really answer the question. How to classify algorithms that are tuned for finite domain? $\endgroup$ – enedil Mar 19 '18 at 11:51
  • 1
    $\begingroup$ @enedil That's not what you asked. Anyway, I'm not aware of any standard terminology beyond using exact costs. Classic theory of algorithms and complexity rarely consider this scenario. $\endgroup$ – Raphael♦ Mar 19 '18 at 12:40
  • 1
    $\begingroup$ @enedil, one possible approach is to make finite automaton for it. But in reality almost all problems on finite domains are just subcases of arbitrary large problems where all parameters are fixed. $\endgroup$ – rus9384 Mar 19 '18 at 12:45
1
$\begingroup$

Let $s$ be the number of states that the Turing machine can be in, including the value of the machine's internal register, the contents of writable tapes, and the locations of the heads. As the machine is deterministic, if it were to enter the same state twice in one run, its sequence of instructions following each step entering that state would have to be the same; therefore it would run forever. Thus the machine can never enter the same state twice so the machine runs in time $O(s)$.

If the machine has $r$ possible values of its internal register, a total of $c$ writable cells each containing a value from an alphabet of size $a$, and tapes of length $l_1, \ldots, l_t$ then it's easy to see that $s \le S \equiv r \cdot a^c \cdot l_1 \cdot \ldots \cdot l_t$. Then the machine runs in time $O(s)$ so it runs in time $O(S)$.

If you treat $r$, $c$, $a$, and $l_1 \ldots l_t$ as constants then $O(S) = O(1)$. However, if you treat them as variables then you can use the formula incorporating them.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.