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?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks, but that doesn't really answer the question. How to classify algorithms that are tuned for finite domain? $\endgroup$ Commented Mar 19, 2018 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$ Commented Mar 19, 2018 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$ Commented Mar 19, 2018 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.