Prove that any algorithm that has sublinear time have a constant time complexity?

Question

This exercise is taken from Goldreich's textbook of "Computational Complexity - A Conceptual Perspective", first ed., p.140.

Exercise 4.3: Referring to any reasonable model of computation and assuming that the input length is not given explicitly, prove that any algorithm that has sub-linear time complexity actually has constant time complexity?

Here is the note given by Oded:

Guideline: Consider the question of whether or not there exists an infinite set of strings S such that invoked on any input $x \in S$ the algorithm reads all of x. Note that if S is infinite then the algorithm cannot have sub-linear time complexity, and prove that if S is finite then the algorithm has constant time complexity.

For definition of sublinear time, see here.

This is how I show it: Since we strictly read less than the size of the input |x|, then it is necessarily that we read some of the input, let's say 1, 2, ..., k where k < |x|. Since k is not part of the input, therefore time complexity of this algorithm is O(1). Is my conclusion right? If not, then why?

As you notice, I didn't use the hint since I didn't know how to show if S is finite, then the algorithm has a constant time.

Answer 1

I think to make this work we need to work in a model of computation where the input string is read sequentially. That is, in order to read the $i$'th character of the input string $S$, we first need to read characters number $1,2,\ldots,i-1$. In what follows I also assume that every substring of a valid input is a valid input (this in particular implies the fact that the length of the string cannot be explicitely encoded in, say, the first $O(\log n)$ bits of the input).

Let $S$ be the set of strings such that invoked on any input $x\in S$ the algorithm $A$ reads all of $x$. As the guideline suggests $S$ must be finite, as otherwise $A$ cannot be sublinear.

Now, let $k$ be the length of the longest string in $S$. I claim that $A$ never reads more than $k$ characters of its input. Indeed, suppose there is some input $x$ such that $A$ reads $k'>k$ characters when invoked on $x$. Let $y$ be the string consisting of the first $k'$ characters in $x$ (this is where I use the assumption that every substring of a valid input is a valid input). Because $A$ reads only the first $k'$ characters when invoked on $x$ it cannot distinguish between $x$ and $y$. In particular, it also reads all $k'$ characters when invoked on $y$. Thus, $y\in S$ and $y$ is of size $k'>k$, which contradicts the definition of $k$. We conclude that our assumption was wrong, and $A$ never reads more than $k$ characters of its input.

Because $A$ never reads more than $k$ characters of the input, it has a finite (constant) number of distinct possible executions. Thus, its worst-case time-complexity is also constant.

(I implicitly assumed a deterministic model of computation here, but it isn't hard to make the argument work under the presence of randomness, both for worst-case and expected time-complexity)