algorithm time analysis "input size" vs "input elements"

Question

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?

Answer 1

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.

Answer 2

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.