5
$\begingroup$

I am unable to find a clear definition of term "size of the instance" when considering some algorithmic problem. I came accross a definition that said, that "Size of the instance corresponds to the size of the input array of numbers (in case the input is numeric) or size of the representation of the input."

Is the size of the instance simply size of the input? Or is it size of all the structures used in the algorithm (in that case, it would be the space complexity, right?).

Lets explain it on a specific problem:

a) I have an array of n numbers and I have to sort them in non-decreasing order.

  • So the size of the instance is n (those n numbers I have to sort - using for example BubbleSort). Is the size different for some other sort that uses some additional arrays during the sorting process?

b) Find strong components of a graph with n vertices and m edges.

  • Is it simply n+m? Or n+2m (if I represent edges by 2*m array)? Or do I have to consider all structures used in my algorithm (in this case it would be Tarjan, I guess).

Thank you for clarification!

$\endgroup$
7
$\begingroup$

Unfortunately, there is no single definition of the size of instance. But if there were, it would be the size of the input in bits. Whenever we talk about Turing machines, we have to slightly change this to the size of the input in tape symbols.

Things get more complicated for models like the RAM machine, in which numbers are opaque. If the input consists of arbitrary-precision numbers, then the inputs size is the number of input numbers. This is again a variation on the earlier definition, since in this model, every memory cell contains an entire number.

Summarizing, the size of the input is always the number of cell / tape positions containing the input, but the interpretation of this quantity depends on the model.

More concretely, in your first example, the input includes the input array of length $n$ as well as the number $n$, so the input length should be at least $n+1$. The model in question here is the RAM model. If it were the Turing machine model, the size of the input would depend on the size of the integers being sorted.

In your second example, it depends on the exact encoding. In the RAM model, you can encode a graph with $n$ vertices and $m$ edge using $O(m)$ cells. In the Turing machine model, you can encode a graph using $O(n^2)$ cells or $O((m+1)\log n)$ cells, using the dense and sparse encodings, respectively. Sometimes the input encoding affects the running time, and in that case the algorithm would expect the input in some specific encoding, and you would get the input length from this encoding. Notice that I don't bother calculating the exact input length – almost always asymptotics are enough.

$\endgroup$
3
$\begingroup$

The size of the instance of a problem is the size of the representation of the input. For the Turing model, this is the number of cells used to write the encoded input on the tape.

Generally, we talk about bits and binary encoding of information. We could actually use any base $b$ to encode our input, for $b\geq 2$. This is the same as saying it does not matter whether we allow our Turing machine $M$ to have an arbitrary sized tape alphabet $\Gamma$, because we can construct an equivalent (computes the same function) Turing machine $M^\prime$ with $\Gamma=\{0,1,\square\}$ with polynomial overhead. (If $f$ is computable in time $T(n)$ by $M$ for some time-constructible $T:\mathbb{N}\rightarrow\mathbb{N}$ then $f$ is computable in time $C\log|\Gamma|T(n)$ by $M^\prime$ for some constant $C$. This means the Turing machine model is robust.)

The encoding is important, especially when we are considering problems that have integers as their input (e.g. Integer Factorisation).

If we use an encoding with base $b=1$, i.e. a unary representation, this actually changes things. In particular, the Integer Factorisation problem is not known to be computable in polynomial time (see P versus NP) for a binary encoding, but it can be computed in linear time if the input is given in unary encoding.

[1] Arora, Sanjeev, and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009. (c.f. Exercise 1.15 and Claim 1.5)

$\endgroup$

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.