7.3.1 Input size

Procedure inputs may be many different types: Numbers, Lists of Numbers, Lists of Lists, Procedures, etc. Our goal is to characterize the input size with a single number that does not depend on the types of the input.

We use the Turing machine to model a computer, so the way to measure the size of the input is the number of characters needed to write the input on the tape. The characters can be from any fixed-size alphabet, such as the ten decimal digits, or the letters of the alphabet. The number of different symbols in the tape alphabet does not matter for our analysis since we are concerned with orders of growth not absolute values. Within the $O$, $\Omega$, and $\Theta$ operators, a constant factor does not matter (e.g., $\Theta(n) \equiv \Theta(17n+523)$). This means is doesn't matter whether we use an alphabet with two symbols or an alphabet with 256 symbols. With two symbols the input may be 8 times as long as it is with a 256-symbol alphabet, but the constant factor does not matter inside the asymptotic operator.

Thus, we measure the size of the input as the number of symbols required to write the number on a Turing Machine input tape. To figure out the input size of a given type, we need to think about how many symbols it would require to write down inputs of that type.

Booleans. There are only two Boolean values: true and false. Hence, the length of a Boolean input is fixed.

Numbers. Using the decimal number system (that is, 10 tape symbols), we can write a number of magnitude $n$ using $\log_{10} n$ digits. Using the binary number system (that is, 2 tape symbols), we can write it using $\log_{2} n$ bits. Within the asymptotic operators, the base of the logarithm does not matter (as long as it is a constant) since it changes the result by a constant factor. We can see this from the argument above --- changing the number of symbols in the input alphabet changes the input length by a constant factor which has no impact within the asymptotic operators.

Lists. If the input is a List, the size of the input is related to the number of elements in the list. If each element is a constant size (for example, a list of numbers where each number is between 0 and 100), the size of the input list is some constant multiple of the number of elements in the list. Hence, the size of an input that is a list of $n$ elements is $cn$ for some constant $c$. Since $\Theta(cn) = \Theta(n)$, the size of a List input is $\Theta(n)$ where $n$ is the number of elements in the List. If List elements can vary in size, then we need to account for that in the input size. For example, suppose the input is a List of Lists, where there are $n$ elements in each inner List, and there are $n$ List elements in the main List. Then, there are $n^2$ total elements and the input size is in $\Theta(n^2)$.