0
$\begingroup$

What is the correct term for the maximal running time of a given algorithm on all inputs of length bounded by given $n$, on which the algorithm halts? Assume, if necessary, that the halting problem of the given algorithm is decidable (with unknown complexity).

How is this time function of $n$ called? Is it studied in complexity theory, or does one only consider the running time of universally halting algorithms?

$\endgroup$
  • 1
    $\begingroup$ My guess is that researchers wouldn't typically consider this concept because a non-total program that takes at most t(n) time when it does halt can be turned into a program takes at most t(n) time and halts on all inputs. The idea is to add a clock. The new program increments the clock for each step of the computation and halts when the clock reaches t(n). (This is ok as long as we can always efficiently check whether or not the clock has reached t(n). In other words, as long as t(n) is efficiently constructible i.e. time-constructible.) $\endgroup$ – Michael Wehar Feb 5 '15 at 5:11
  • 1
    $\begingroup$ Thanks for a meaningful comment. In fact, i am refereeing a paper where the authors talk about this running time without calling it so, but calling it complexity for some reason, in a context of a non-total program for which the halting problem is decidable. $\endgroup$ – Alexey Feb 5 '15 at 9:48
  • $\begingroup$ You're welcome. It sounds like the situation you are referring to is more involved. In that case, it's possible that the concept has more value, but I'm not sure. $\endgroup$ – Michael Wehar Feb 5 '15 at 16:42
  • $\begingroup$ No, assuming that the halting problem is decidable does not lead to a contradiction, there exist partial algorithms with decidable halting problem. $\endgroup$ – Alexey Feb 6 '15 at 10:43
  • 1
    $\begingroup$ I can't answer with any authority, but I suspect they'd just call it "runtime", assuming that everybody understands what is being talked about. (Complexity theory (ab)uses a number of terms in this way.) Also, runtime of non-deterministic machines has a similar problem (some computations take longer than others) and there we just say "runtime", expecting people to be a) aware of what type the discussed machine is and b) have the appropriate definition in mind (or look it up). $\endgroup$ – Raphael Feb 8 '15 at 14:25
1
$\begingroup$

Given an algorithm $A$ (on inputs from some set $X$), we define the runtime function to be $T_A(x) : X \to \mathbb{N} \cup \{\infty\}$ so that

$\qquad T_A(x) = \begin{cases} \text{number steps } A(x) \text{ takes},\ \ &A(x)\!\downarrow \\ \infty, &A(x)\!\uparrow \end{cases}$

for all $x \in X$. I denote with $A(x)\!\downarrow$ that $A$ terminates on $A$, and with $A(x)\!\uparrow$ the opposite. Note that the number of steps an algorithm takes on an input depends on the computational model you choose, but we can leave that abstract here.

Now, the common way to define worst-case runtime is

$\qquad\displaystyle T_A^{\mathrm{WC}}(n) = \max \{ T_A(x) \mid x \in X, |x| = n\}$

which of course yields $\infty$ if there is any input of the given size for which $A$ loops. You want

$\qquad\displaystyle T_A^{\mathrm{WC\downarrow}}(n) = \max \{ T_A(x) \mid x \in X, |x| = n, A(x)\!\downarrow\}$.

I don't know an established name for that one, but if I were to need one I'd go with terminating-worst-case runtime¹. That said, you probably use only one notion of runtime most of the time, so you can do as most authors do and say something along the lines of:

From here on out, we always mean $T_A^{\mathrm{WC\downarrow}}$ when we write "runtime" unless otherwise specified.

So yes, just use runtime but make very clear what you mean by that.


  1. You notice that the definition of $T_A^{\mathrm{WC\downarrow}}$ assumes that there is at least one input of every size for which $A$ terminates. You should handle the case if that fails.
$\endgroup$
  • $\begingroup$ Shouldn't it actually be "$|x|\le n$" in those definitions? $\endgroup$ – Alexey Mar 17 '15 at 18:28
  • $\begingroup$ Not if you want "exact" runtime functions. With $\leq$, you won't see oscillations; you smooth some stuff out. In particular, you may smooth over undefined values in your case, which would be particularly bothersome. $\endgroup$ – Raphael Mar 17 '15 at 20:55

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.