6
$\begingroup$

I've seen this statement mentioned a few times here on cs.stackexchange and have not been able to follow the logic. The statement is 'If you restrict the input size of the problem then solving that problem (even SAT) can be done in O(1)'.

So say I restrict the size of SAT to N = 1000, now that means that solving SAT for any N <= 1000 can be done in O(1)? That doesn't quite follow.

Can someone shed some light on this concept?

$\endgroup$
  • $\begingroup$ for restricted size you can store the inputs and their respective outputs in a database and get the output of the given input in O(1). But this is not theoretical and in practice can't be used for all cases as 2^1000 is to big to store for SAT. $\endgroup$ – atayenel Jul 9 '16 at 20:54
  • $\begingroup$ Not sure that is true: suppose we have an algorithm that solves SAT for all N <=1000. We could not store the input/output because there is an infinite number of sets of 1000 numbers. $\endgroup$ – C Shreve Jul 9 '16 at 23:50
  • $\begingroup$ for boolean SAT is it 2^1000 input sets. But yeah it is impossible to store that many numbers. That's why it is a comment rather than an answer $\endgroup$ – atayenel Jul 10 '16 at 0:24
  • $\begingroup$ The statement would not hold if the problem is not computable. Ex: Print all real numbers bigger than an integer X. The statement: "If you restrict the input size of the problem then solving that problem can be done in O(1)" $\endgroup$ – rdllopes Jul 14 '16 at 12:53
7
$\begingroup$

If the input size is limited, then you can calculate the solutions to all problems. This will take a very, very, very long time. But once these solutions have been calculated, you can just lookup the solution of any problem in your list of solutions.

Even worse: Look at the definition of Big-O. The claim is that there is a constant $c > 0$, and an integer $N_0 > 0$ such that for every problem with a size $N > N_0$, the problem can be solved in less than $c * 1$ steps. If you restrict SAT to $N ≤ 1000$, then this is trivially true with $c = 1$ and $N_0 = 1001$. There are no problems with a size > 1000, therefore all the (nonexisting) problems with a size ≥ 1001 can be solved in one step.

$\endgroup$
  • 3
    $\begingroup$ " then you can calculate the solutions to all problems" -- we don't need to do that for the argument. There exists a table with all the solutions and has finite size, hence there exists an algorithm with $O(1)$ running-time for the problem. We don't need to write it down. $\endgroup$ – Raphael Jul 12 '16 at 8:56
4
$\begingroup$

If you restrict any problem at all to inputs of size at most $N$, for some fixed constant $N$, then the language is finite, so it's regular. But don't regular languages take linear time? Not in this case: as soon as you see an $(N+1)$st input character, you can reject because the input isn't an instance of length at most $N$. So you only need to look at a constant number of characters to decide any input.

Note that this applies to any problem. The problem doesn't even have to be computable.

$\endgroup$
  • $\begingroup$ Maybe there is a terminology mix up here: there are an infinite number of strings required to represent every set of 1000 integers (suppose we are talking about SubSet Sum) - so this language would not seem to be finite. $\endgroup$ – C Shreve Jul 10 '16 at 0:02
  • 4
    $\begingroup$ The size of the input is the number of bits required to represent it. It's not that you're restricting to every set of 1000 integers, but to every set of integers that can be described in 1000 bits. There are only finitely many of those. $\endgroup$ – David Richerby Jul 10 '16 at 8:28
  • $\begingroup$ That does clear things up: there is a difference between restricting the number of inputs to a problem (this can still be an infinite language) and restricting the total size of input to the problem (this would be a finite language). $\endgroup$ – C Shreve Jul 10 '16 at 16:01
  • $\begingroup$ @CShreve yes it does, both answer and comments show exactly the second option you have listed. $\endgroup$ – Evil Jul 11 '16 at 16:39
  • 1
    $\begingroup$ @rdllopes But you can only encode at most $2^n$ different Diophantine equations in $n$ bits, whcih is the whole point. For each of those $2^n$ equations, you can figure out whether or not there's a solution and program the computer to accept or reject as appropriate. It doesn't matter that you can't figure out if general Diophantine equations have solutions; you only need to figure out those $2^n$ specific ones, and then program the computer to accept the equations coded by, say, 1, 487, 503, 2374, ... and reject all the others (including anything that takes more than $n$ bits to write out). $\endgroup$ – David Richerby Jul 15 '16 at 19:49
3
$\begingroup$

While the first part of gnasher729's answer gives a good intuition for how to answer any such problem in a time that anyone can see is clearly $O(1)$, there's another way to see that the $O(1)$ claim holds even if we don't do any precomputation and storing of answers.

The thing about bounding the input size by some constant $k$ is that, if you do this, then regardless of what algorithm you use to solve the problem, provided that it eventually terminates on every input of size $\le k$, its worst-case execution time on a size-$n$ input for any $n \le k$ can be described by some function $f(n)$ -- and if all the things that you put into a function are bounded by constants, then what comes out is also bounded by a (probably different, possibly vastly greater) constant.

The overall worst-case execution time for such an algorithm is then just the maximum of $f(n)$ over all $0 \le n \le k$ -- and the maximum of a finite number of numbers, each of which is bounded by the same constant $c$, is also bounded by $c$.

IOW, even if the algorithm computes everything "the usual way" instead of precomputing all possible answers and storing them (or even if it computes them in "the dumbest, brute-forciest possible way"), the execution time can still be said to be $O(1)$.

$\endgroup$
0
$\begingroup$

We have a finite number of possible inputs, and a solvable problem. Consider any algorithm that solves this problem. Either the algorithm's run time is O(1) or it is not O(1). If it is O(1), then our proof is done.

So what if it's not O(1)? Well, since there are only a finite number of possible inputs, there must be some number of steps that's sufficient for the algorithm to solve any single input, call that N.

We can now construct an O(1) algorithm:

1) Solve the input. Call the number of steps required P.

2) If P is less than N, do nothing N-P times.

This algorithm can solve any possible input in precisely the same number of steps. Thus it is an O(1) algorithm.

$\endgroup$
-1
$\begingroup$

The big O notation is to approximate to the upper bound (worst case) and gives an idea about how good is the algorithm.

O(1) is the constant-time (time of execution is known in advance) and it is the best one. The O(1) is when T(N) expression does not contain the input size N.

When restricting the size of the input N (N<=C) and as we ara approximating to upper bound, in T(N) we can replace N by its known upper bound the constant C which gives us O(1).

$\endgroup$
  • 2
    $\begingroup$ Actually, strictly speaking Big Oh is not "meant to measure the worst case", it's not even necessarily related to the analysis of algorithms. $\endgroup$ – Juho Jul 13 '16 at 20:47
  • $\begingroup$ If I make O (n) dollars profit from selling n cars, then O (n) isn't worst case but best case :-) $\endgroup$ – gnasher729 Jul 14 '16 at 7:53
  • $\begingroup$ @gnasher729 instead of saying I make O(n) dollars you should say I spend O(n) dollars! $\endgroup$ – flatrach Jul 14 '16 at 10:05

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.