13
$\begingroup$

I'm still a bit confused with the terms "input length" and "input size" when used to analyze and describe the asymptomatic upper bound for an algorithm

Seems that input length for the algorithm depends a lot of the kind of data and the algorithm you are talking about.

Some authors refer to input length to the size of characters that are required to represent the input, so "abcde" if use as input set in an algorithm will have an "input length" of 6 characters.

If instead of characters we have number (integers for instance) then sometimes the binary representation is use instead of characters so the "input length" is calculated as $N*log(L)$ (Being L the Max number in the input set).

There are other problems that even if the input set are numbers, they describe the "input length" as "decision variables", so for a input set of length N with numbers in the range $0-2^{32}$ the input length is just N (subset sum for instance), or even more complicate the number of binary place values that it takes to state the problem (what I believe is just the same as $N*log(L)$)

So:

  • it depends on the algorithm?
  • What means and when to use each input length "version"
  • Is there are some rule I can use to decide which one to use?
$\endgroup$
9
$\begingroup$

In the most formal sense, the size of the input is measured in reference to a Turing Machine implementation of the algorithm, and it is the number of alphabet symbols needed to encode the input.

This is of course rather abstract, and is very difficult to work with in practice, or at least very annoying - we would need to consider how we're going specify delimeters etc. etc. What happens normally in practice then is that we look for a proxy measurement of the size of the input - something more convenient and accessible, but that does not cause any mathematical problems in our analysis.

Using your "abcde" example, it would normally be the case that the alphabet we use for the input is small, so even using the proxy measurement of $5$ characters, we known that even on a Turing Machine, we can, if we bothered, specify an input encoding that would convert "abcde" to some encoded form that had length at most $5\times c$ for some constant $c$. This expansion by a constant would typically make no difference in our asymptotic analysis, as we routinely discard constant factors.

In a different case, we often measure the size of an input graph by the number of vertices $n$. Clearly if we want to specify arbitrarily large graphs, the size of the encoded input is not simply $n$ - what happened to the edges, for example? What we do know is that we can use a reasonable encoding scheme that represents the graph in $N = c\cdot n^{2}\log n$ bits. This is a bit more of an expansion than constant, but in a lot of interesting cases, we're only dealing with things at a granularity of polynomials, and polynomials compose nicely in a lot of ways - in particular, as an example, if we determine that our running time is $O(p(n))$ where $p$ is a polynomial, then we know that there is some polynomial $p'$ such that $O(p(n)) = O(p'(N))$, so when we move back to the formal measure of the input, we're still in polynomial time.

A place where this might fall down is when you are working with numbers. As a number with magnitude $m$ can be encoded in $n = O(\log m)$ bits, if our running time were $O(m)$, this would be $O(2^{n})$ - exponential in the actual input size - which would make the magnitude $m$ a bad choice for a proxy for the input size if we wanted to talk about membership in $\mathcal{P}$ for example (when you come to Strongly-$\mathcal{NP}$-complete and Weakly-$\mathcal{NP}$-complete, remember this). On the other hand, if all we were interested in was decidability, then it would be a good enough proxy measure.

So while there's no stated rule for picking a proxy measure for the input size, the requirement is that the expansion or contraction of the proxy size compared to the input size should be compatible with what you're trying to prove. As a rule of thumb, constant factor changes almost never matter, small polynomial factors are normally fine and work for most of the basic theory that you see, large polynomial factors might still work in for theory, but can be a nasty surprise in practice, and exponential amounts of change are normally way too extreme.

$\endgroup$
  • $\begingroup$ Thanks for the answer. Really interesting the part you talk about the selection of the right proxy to talk about membership in P or NP for the input, that could be a complete new question! Besides that, and coming back to the former question. Which one in your opinion would be then the best proxy for an algorithm that its input is a set of integers? I guess Maybe it will depend on the algorithm? I see 3 potential options: N (being the length of the set) N*Log(L) (L being the max value) and Log(Sum(set)). $\endgroup$ – Jesus Salas Dec 6 '14 at 8:48
  • $\begingroup$ @JesusSalas, it definitely can depend on what you do with them, but $N\log L$ would be the simplest "close enough to the TM encoding" answer, but it can still be interesting to look at the running time in terms of $N$, or maybe $N$ and the magnitude of the largest number - of course this is just $2^{\log L}$, but sometimes it can be easier to analyse things with non-obvious measures. $\endgroup$ – Luke Mathieson Dec 6 '14 at 9:00
  • $\begingroup$ This covers the bases but there are some inaccuracies. Representing "abcde" on a Turing machine doesn't take $5c$ characters: it takes five characters if you choose the right alphabet. And you don't need $cn^2\log n$ bits to represent an $n$-vertex graph: the adjacency matrix is exactly $n^2$ bits. $\endgroup$ – David Richerby Dec 6 '14 at 9:38
  • $\begingroup$ Maybe when to use N or N log L could depend on the cost for the algorithm to operate on each input element. I guess that if we have an assumption that the algorithm use constant time to do its work on each input element independently of its size in bits (and this is not abused), then N is probably the right one, resulting in O(N). In the other hand if the input element size in bits increase the operation cost then N log L seems more accurate as the we should express in the upper bound what properties from the input are involved in growth $\endgroup$ – Jesus Salas Dec 6 '14 at 9:52
  • $\begingroup$ @DavidRicherby yes, if you get to choose the alphabet it takes $5$ symbols, but this is just where $c=1$, if for other reasons we have a different alphabet, say binary, seeing as it's much more useful to be able to say we can encode everything in binary without loss of generality, then $c = \log_{2}5$, but it's easy, and interesting to see that it's relatively easy to do it with any not-insane alphabet within a constant factor of $5$. Also, true, you may not need $O(n^{2}\log n)$ bits, but it is a pretty robust upper bound that can deal with both normal encodings. $\endgroup$ – Luke Mathieson Dec 6 '14 at 9:56
8
$\begingroup$

It depends on your model of computation and also on the unfortunately sometimes on the algorithm itself.

  • If your model of computation is a Turing machine, then the size of the input is the number of cells occupied by the input. So if your input is $ababcd$ then the input has length 6.
  • If your model is the RAM then the size of the input is the number of registers/memory cells where the input initially stays. This might be misused since you could technically write the whole input in one register. However then computations are more costly if you use the logarithmic costs model.
  • If your model of computation is a word-RAM, then you also count the memory cells, but they can only store $w$-bit integers, for $w$ being a parameter of your model.

However many algorithms are not measured with respect to the "actual" input size. Then you have to carefully look, what the statement of the analysis refers to.

  • Often you have a implicit assumption with the problem. When saying that it takes $O(n\log n)$ time to sort $n$ items then you assume that two items can be compared in $O(1)$ time. Of course if you sort, say $n$ very long strings, then this might not be true.
  • For conventional reasons you measure sometimes with respect to a different parameter of the input. For example matrix multiplication is typically analyzed for multiplying two $n\times n$ matrices.

Some rule: Use whatever you want, but make it clear in the statement of the result. So just say what $n$ exactly is, if there is a chance of misunderstanding.

$\endgroup$
  • 1
    $\begingroup$ Say what $n$ is regardless of whether there's a chance of misunderstanding! "The algorithm runs in time $O(n^3)$" is meaningless if $n$ hasn't been defined, even if "$n$ is the length of the input" is the only sane guess. $\endgroup$ – David Richerby Dec 6 '14 at 9:40

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.