2
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ Could you say precisely which textbook (and edition) you are referring to? Also, does the exercise say you should prove this or "prove or disprove"? Because without the precise context this claim seems wrong. $\endgroup$
    – Tassle
    May 23, 2021 at 13:04
  • $\begingroup$ @Tassle Thank you for your note, I updated the question. The question asks for "prove". $\endgroup$
    – user777
    May 23, 2021 at 20:38
  • $\begingroup$ I don't see a proof here. $\endgroup$ May 23, 2021 at 21:08
  • $\begingroup$ You don't necessarily strictly read less than the size of the input. For example, an algorithm running in time $1000\sqrt{n}$ is sublinear, but for small inputs it has enough time to read the entire input. $\endgroup$ May 23, 2021 at 21:12

1 Answer 1

4
$\begingroup$

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)

$\endgroup$
3
  • $\begingroup$ I notice you don't make use of the "input length not given explicitly" assumption, but then I don't know how to interpret it anyway -- I guess it means something like "input length cannot be determined by looking at $O(\log n)$ input bits", but it's easy to get around such a narrow definition with a "bad" encoding. $\endgroup$ May 24, 2021 at 1:31
  • $\begingroup$ @j_random_hacker I interpreted it a bit more strictly as meaning that we need to look at the whole string to know its length. Actually I implicitly made a stronger assumption when defining $y$ : "every substring of a valid input is a valid input". I'll add that explicitly to the answer, thanks for the feedback! $\endgroup$
    – Tassle
    May 24, 2021 at 12:15
  • $\begingroup$ Thank you Tassle! what I understand is that you proved it by contradiction. I think what I give in my question is nevertheless just a statement (i.e. we read some strings of length k which is not part of the input). Question: Do you have any reason why if S is infinite, then it cannot have sublinear time? $\endgroup$
    – user777
    May 25, 2021 at 4:02

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.