2
$\begingroup$

I studied a definition for time complexity: Let $M$ be a deterministic Turing Machine. The running time of $M$ is said to be:

for a function $t: \mathbb{N} \to \mathbb{N}$ ($\mathbb{N}$ is natural number) and for all $x$ belonging to $\Sigma^*$, $M$ halts in at most $O(t(|x|)$ steps.

My question is that $x$ belonging to $\Sigma^*$ means $x$ could very well be $\varepsilon$ (empty string) for which $|x| = 0$. How is $t(0)$ computed as 0 is not a natural number.

$\endgroup$
6
  • 2
    $\begingroup$ en.wikipedia.org/wiki/Natural_number $\endgroup$
    – kaya3
    Commented May 22 at 17:50
  • $\begingroup$ Wikipedia/Is 0 a natural number? That's a fun discussion!! Thanks for the laughs $\endgroup$
    – Stef
    Commented May 22 at 18:36
  • $\begingroup$ Is that word for word the definition in the book? It's weird. "For all x, M halts in at most O(t(|x|)) steps"? If x is already quantified by "for all", then t(|x|) is a constant and it doesn't make sense to talk about big-O... $\endgroup$
    – Stef
    Commented May 22 at 18:39
  • $\begingroup$ @Stef yes, and the same has been mentioned for s(|x|) where 's' is the space complexity function. I think O(t|x|) point is irrelevant in discussion as the entire point of using big-O is to ignore certain stuff like multiplication by constants and lower order terms. What's really bothering me is that I am not able to understand what part of this definition feels weird, is it 0 being a natural number (or not) or is it x belonging to Σ*. $\endgroup$ Commented May 23 at 6:26
  • $\begingroup$ @OM_anand Whether or not |x|=0 is allowed by the definition really couldn't matter less. The only thing important in the definition is what happens in the limit. You could add any arbitrary constraint like |x| > 0 or |x| > 1 or |x| > 42 or |x| > 137 in that definition and the resulting definitions would all be equivalent. What is important in that definition is what happens when |x| grows, not when |x| is small. But the definition is a bit sloppily written. $\endgroup$
    – Stef
    Commented May 23 at 13:22

1 Answer 1

7
$\begingroup$

$\mathbb{N}$ can be defined as the set of non-negative integers 0, 1, 2, ...

You should check the definition in the book you're reading.

However, there is no contradiction regardless of how $\mathbb{N}$ is defined. It might just be a tiny mistake that I'm sure you're able to fix.

$\endgroup$
1
  • $\begingroup$ Thanks for the quick reply. It was mentioned that ℕ here is a "natural number". So I had begun to think that instead of x belonging to Σ* (U Σ^i; i>=0), they would have probably meant x belonging to Σ+(U Σ^i; i>0). Not sure if that fix makes sense. $\endgroup$ Commented May 22 at 9:25

Your Answer

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

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