Exercises · Input size¶
Exercises · Chapter 11 · each solution opens with a click · Chapter 11: Input size · Exercises, volume 4 (PDF)
In the exercises of this chapter the input size is computed with the formulas of the chapter «Input size», summarized below.
The input size \(|I|\) of an instance \(I\) is the total number of bits needed to represent \(I\) in binary:
-
one natural number \(n\ge 1\):
\[ |I|=\lfloor\log_2 n\rfloor+1=\Theta(\log_2 n); \] -
two natural numbers \(n,m\ge 1\):
\[ |I|=\big(\lfloor\log_2 n\rfloor+1\big)+\big(\lfloor\log_2 m\rfloor+1\big)=\Theta\big(\log_2 \max\{n,m\}\big); \] -
an array \(a[1..n]\) of natural numbers (an entry equal to \(0\) uses \(1\) bit):
\[ |I|=\sum_{i=1}^{n}\big(\lfloor\log_2(\max\{1,a[i]\})\rfloor+1\big), \qquad n \le |I| \le n(1+\log_2 M), \]where \(M=\max\{1,a[1],a[2],\dots,a[n]\}\).
A natural number is written with exactly \(k\) bits if and only if \(2^{k-1}\le n\le 2^k-1\).
Exercise 11.1: Input size (E1)
Consider the following input instances:
-
(a) the natural numbers \(n=1\), \(n=13\), \(n=255\), \(n=256\), \(n=1000\), \(n=10^6\);
-
(b) the pairs of natural numbers \((n,m)=(48,18)\) and \((n,m)=(1000,7)\);
-
(c) the arrays \([5,2,4,1,3]\), \([1,1,1,1]\), \([1024,1,1]\), \([0,7,8]\).
Questions
-
Compute the input size \(|I|\) of every instance in (a), and write the binary representation of \(13\), \(255\) and \(256\).
-
Compute the input size of the two instances in (b).
-
Compute the input size of the four arrays in (c). For each array compare \(|I|\) with the number \(n\) of entries and with the upper bound \(n(1+\log_2 M)\), where \(M=\max\{1,a[1],a[2],\dots,a[n]\}\).
-
What is the largest natural number that can be represented with \(|I|=k\) bits? And the smallest natural number \(n\ge 1\) whose input size is \(k\)?
Solution
-
Using \(|I|=\lfloor\log_2 n\rfloor+1\):
\(n\) powers of 2 \(\lfloor\log_2 n\rfloor\) \(|I|\) \(1\) \(2^0\le 1<2^1\) 0 1 \(13\) \(2^3\le 13<2^4\) 3 4 \(255\) \(2^7\le 255<2^8\) 7 8 \(256\) \(2^8\le 256<2^9\) 8 9 \(1000\) \(2^9\le 1000<2^{10}\) 9 10 \(10^6\) \(2^{19}\le 10^6<2^{20}\) 19 20 Binary representations: \(13=(1101)_2\) (4 bits), \(255=(11111111)_2\) (8 bits), \(256=(100000000)_2\) (9 bits). Note that \(255\) and \(256\) differ by \(1\), but their input sizes differ by one bit, because \(256=2^8\) is a power of \(2\).
-
For \((48,18)\): \(2^5\le 48<2^6\) and \(2^4\le 18<2^5\), so
\[ |I|=(5+1)+(4+1)=6+5=11. \]For \((1000,7)\): \(2^9\le 1000<2^{10}\) and \(2^2\le 7<2^3\), so
\[ |I|=(9+1)+(2+1)=10+3=13. \] -
Bits of each entry and total:
array bits per entry \(|I|\) \(n\) \(n(1+\log_2 M)\) \([5,2,4,1,3]\) \(3+2+3+1+2\) 11 5 \(5(1+\log_2 5)\approx 16.61\) \([1,1,1,1]\) \(1+1+1+1\) 4 4 \(4(1+0)=4\) \([1024,1,1]\) \(11+1+1\) 13 3 \(3(1+10)=33\) \([0,7,8]\) \(1+3+4\) 8 3 \(3(1+3)=12\) In all cases \(n\le|I|\le n(1+\log_2 M)\), in agreement with \(|I|=\Omega(n)\) and \(|I|=O(n(1+\log_2 M))\). The upper bound is tight for \([1,1,1,1]\) (all entries equal), while it is far from \(|I|\) for \([1024,1,1]\), where only one entry is large.
-
With \(k\) bits the largest representable number is
\[ (\underbrace{11\dots1}_{k})_2=2^k-1, \]and the smallest number \(n\ge 1\) with \(\lfloor\log_2 n\rfloor+1=k\) is \(n=2^{k-1}=(1\underbrace{0\dots0}_{k-1})_2\). Hence the numbers with input size exactly \(k\) are those with
\[ 2^{k-1}\le n\le 2^k-1. \]For example, for \(k=8\) these are the numbers from \(128\) to \(255\).
Exercise 11.2: Input size (E2)
Consider the following families of input instances, parametrized by a natural number \(n\ge 1\) (or \(k\ge 1\)):
-
(a) the single natural number \(2^k\), and the single natural number \(2^k-1\);
-
(b) the array \(a[1..n]\) with \(a[i]=i\) for every \(i\in\{1, 2, \dots, n\}\);
-
(c) the array \(a[1..n]\) with \(a[i]=2^i\) for every \(i\in\{1, 2, \dots, n\}\);
-
(d) the array \(a[1..n]\) with \(a[i]=n\) for every \(i\in\{1, 2, \dots, n\}\);
-
(e) an array \(a[1..n]\) whose entries are natural numbers smaller than \(2^{32}\), so that each of them can be written with at most \(32\) bits.
Questions
-
Compute exactly the input size of the instances in (a), as a function of \(k\).
-
Compute exactly the input size of the arrays in (c), and express it asymptotically as a function of \(n\).
-
Express asymptotically the input size of the arrays in (d) and (e).
-
For the arrays in (b), compute \(|I|\) for \(n=1,2,3,4,8,16\), and prove that \(|I|=\Theta(n\log_2 n)\).
Solution
-
Since \(\log_2 2^k=k\), the number \(2^k\) has input size
\[ |I|=\lfloor\log_2 2^k\rfloor+1=k+1. \]Since \(2^{k-1}\le 2^k-1<2^k\), we have \(\lfloor\log_2(2^k-1)\rfloor=k-1\) and
\[ |I|=k. \]In both cases \(|I|=\Theta(k)\), while the numerical value is \(\Theta(2^k)\): the value is exponential in the input size.
-
The entry \(a[i]=2^i\) requires \(\lfloor\log_2 2^i\rfloor+1=i+1\) bits, so
\[ |I|=\sum_{i=1}^{n}(i+1)=\frac{n(n+1)}{2}+n=\frac{n(n+3)}{2}. \]For example, for \(n=4\): \(2+3+4+5=14=\frac{4\cdot 7}{2}\). Since
\[ \lim_{n\to\infty}\frac{n(n+3)/2}{n^2}=\lim_{n\to\infty}\frac{1}{2}\left(1+\frac{3}{n}\right)=\frac12\in\R_{>0}, \]we have \(|I|=\Theta(n^2)\) by the limit criterion. Directly, since \(n^2 \le n(n+3) \le 4n^2\) for every \(n \ge 1\), the constants \(c_1=\frac12\), \(c_2=2\) and \(n_1=1\) give \(\frac12 n^2\le|I|\le 2n^2\). Here the entries do not use a constant number of bits, and the input size is quadratic in the number of entries.
-
(d) Every entry is equal to \(n\) and uses \(\lfloor\log_2 n\rfloor+1\) bits, so
\[ |I|=n\big(\lfloor\log_2 n\rfloor+1\big)=\Theta(n\log_2 n), \]because \(\lfloor\log_2 n\rfloor+1=\Theta(\log_2 n)\) (Observation on one natural number), multiplied by \(n\).
(e) Every entry uses at least \(1\) and at most \(32\) bits, so
\[ n\le|I|\le 32n, \]and \(|I|=\Theta(n)\). This is the hypothesis “every entry uses a constant number of bits” of the corollary on entries of constant size. (If every entry is stored in a memory word of exactly \(32\) bits, the number of stored bits is \(32n\), again \(\Theta(n)\).)
-
The entry \(a[i]=i\) uses \(\lfloor\log_2 i\rfloor+1\) bits:
\(n\) \(|I|\) 1 \(1\) 2 \(1+2=3\) 3 \(1+2+2=5\) 4 \(1+2+2+3=8\) 8 \(1+2+2+3+3+3+3+4=21\) 16 \(21+7\cdot 4+5=54\) Upper bound. Since \(i\le n\), each entry uses at most \(\lfloor\log_2 n\rfloor+1\le\log_2 n+1\le 2\log_2 n\) bits for \(n\ge 2\), so
\[ |I|\le 2n\log_2 n,\qquad \forall n\ge 2. \]Lower bound. Each entry uses at least \(\log_2 i\) bits (since \(\lfloor\log_2 i\rfloor+1\ge\log_2 i\)). Keeping only the indices \(i\ge \lceil n/2\rceil\), which are at least \(n/2\) and are at least \(n/2\) in number,
\[ |I|\ge\sum_{i=\lceil n/2\rceil}^{n}\log_2 i\ge \frac n2\log_2\frac n2=\frac n2(\log_2 n-1)\ge \frac n4\log_2 n, \]where the last inequality holds when \(\log_2 n-1\ge\frac12\log_2 n\), i.e., for \(n\ge 4\).
Therefore, with \(c_1=\frac14\), \(c_2=2\) and \(n_1=4\),
\[ 0\le \frac14\,n\log_2 n\le |I|\le 2\,n\log_2 n,\qquad\forall n\ge 4, \]i.e., \(|I|=\Theta(n\log_2 n)\). (Check: for \(n=16\), \(\frac14\cdot 16\cdot 4=16\le 54\le 2\cdot 16\cdot 4=128\).)
Exercise 11.3: Input size (E3)
Consider the following algorithm, and recall the PrimalityTest algorithm (trial division by \(d = 2, 3, \dots, \lfloor\sqrt n\rfloor\)), whose number of steps in the worst case (\(n\) prime) is \(S(n)=3\lfloor\sqrt n\rfloor+1\), with the body of its while loop executed \(\lfloor\sqrt n\rfloor-1\) times.
Questions
-
Compute the number of steps \(S(n)\) of
SumUpToand determine its worst-case running time \(T(|I|)\). Is the algorithm polynomial? -
Propose an algorithm that computes the same output with a constant number of steps (assume that arithmetic operations take a constant number of steps). Is it polynomial?
-
Prove that
PrimalityTestis exponential in \(|I|\), even though \(S(n)=\Theta(\sqrt n)\) is “sub-linear” in the value \(n\). -
Give an upper bound on the number of iterations of the while loop of
PrimalityTestfor a prime number \(n\) of \(32\) bits and of \(64\) bits. What happens to the number of iterations when the input size doubles?
Solution
-
The number of times each line of code is executed is:
-
Line 2 is executed \(1\) time
-
Line 3 is executed \(1\) time
-
Line 4 is executed \(n+1\) times
-
Line 5 is executed \(n\) times
-
Line 6 is executed \(n\) times
-
Line 8 is executed \(1\) time
Therefore
\[ S(n)=1+1+(n+1)+n+n+1=3n+4=\Theta(n). \]The input is a single natural number, so \(|I|=\lfloor\log_2 n\rfloor+1=\Theta(\log_2 n)\): there exist \(c_1,c_2>0\) such that, for all sufficiently large \(n\),
\[ c_1\log_2 n\le|I|\le c_2\log_2 n \quad\Longleftrightarrow\quad 2^{\frac{1}{c_2}|I|}\le n\le 2^{\frac{1}{c_1}|I|}. \]Since \(a_1n\le S(n)\le a_2 n\) for some \(a_1,a_2>0\),
\[ a_1 2^{\frac{1}{c_2}|I|}\le S(n)\le a_2 2^{\frac{1}{c_1}|I|}, \qquad\text{hence}\qquad T(|I|)=2^{\Theta(|I|)}, \]since the constant factors \(a_1\) and \(a_2\) are absorbed in the exponent (Observation «constant factors in the exponent» of the chapter). The worst case can also be computed exactly. The inputs of size \(|I|\) are the numbers \(n\) with \(2^{|I|-1}\le n\le 2^{|I|}-1\), and \(S(n)=3n+4\) is largest for \(n=2^{|I|}-1\), so
\[ T(|I|)=3\big(2^{|I|}-1\big)+4=3\cdot 2^{|I|}+1 . \]SumUpTois linear in the value \(n\) but exponential in the input size: it is not polynomial. -
-
By Gauss' formula, \(1+2+\cdots+n=\dfrac{n(n+1)}{2}\). The algorithm “return \(n(n+1)/2\)” executes a constant number of steps (one sum, one product, one division, one return), so \(T(|I|)=\Theta(1)=O(|I|^0)\): it is polynomial.
-
The input is a single natural number, so as above \(2^{\frac{1}{c_2}|I|}\le n\le 2^{\frac{1}{c_1}|I|}\). Taking square roots (all terms are positive),
\[ 2^{\frac{1}{2c_2}|I|}\le\sqrt n\le 2^{\frac{1}{2c_1}|I|}. \]Since \(S(n)=\Theta(\sqrt n)\), there exist \(a_1,a_2>0\) with \(a_1\sqrt n\le S(n)\le a_2\sqrt n\), hence
\[ a_1 2^{\frac{1}{2c_2}|I|}\le S(n)\le a_2 2^{\frac{1}{2c_1}|I|}, \qquad\text{hence}\qquad T(|I|)=2^{\Theta(|I|)}, \]since the constant factors \(a_1\) and \(a_2\) are absorbed in the exponent (Observation «constant factors in the exponent» of the chapter). Being sub-linear in \(n\) does not help: \(\sqrt n=2^{\frac12\log_2 n}\) is still exponential in the number of bits \(\log_2 n\). The algorithm is not polynomial: for every constant \(k\), \(\lim_{|I|\to\infty}2^{c|I|}/|I|^k=+\infty\) for any \(c>0\).
-
The while loop is executed \(\lfloor\sqrt n\rfloor-1\) times for a prime \(n\).
-
\(32\) bits: \(n<2^{32}\), so \(\sqrt n<2^{16}=65\,536\) and the loop executes fewer than \(65\,536\) iterations.
-
\(64\) bits: \(n<2^{64}\), so \(\sqrt n<2^{32}=4\,294\,967\,296\) and the loop executes up to about \(4.3\cdot 10^{9}\) iterations.
When the input size doubles (from \(32\) to \(64\) bits) the bound on the number of iterations is squared (\(2^{16}\to 2^{32}\)), while for a polynomial algorithm with \(T(|I|)=\Theta(|I|^k)\) it would only be multiplied by the constant \(2^k\).
-
Exercise 11.4: Input size (E4)
Consider the following two algorithms. Both contain two nested loops.
Questions
-
Compute the number of steps \(S(n)\) of
CountPairsand its worst-case running time \(T(|I|)\). -
Compute the number of steps \(S(n)\) of
CountInversionsin the worst case and its worst-case running time \(T(|I|)\), in general and under the hypothesis that every entry uses a constant number of bits. -
Both algorithms have \(S(n)=\Theta(n^2)\). Explain why one is polynomial and the other is exponential in the input size.
-
Suppose that
CountInversionsalso receives the number \(n\) as part of the input. Compute \(|I|\) for \(n=5\), \(a=[5,2,4,1,3]\), and explain why the conclusion of question 2 does not change.
Solution
-
The number of times each line of code is executed is:
Therefore
\[ S(n)=3+(n+1)+2n+n(n+1)+2n^2=3n^2+4n+4=\Theta(n^2). \]The input is a single natural number, so \(|I|=\Theta(\log_2 n)\) and, as for every single-number input, \(2^{\frac{1}{c_2}|I|}\le n\le 2^{\frac{1}{c_1}|I|}\) for some \(c_1,c_2>0\). Squaring,
\[ 2^{\frac{2}{c_2}|I|}\le n^2\le 2^{\frac{2}{c_1}|I|}, \]and since \(a_1n^2\le S(n)\le a_2n^2\) for some \(a_1,a_2>0\), absorbing the constant factors in the exponent (Observation «constant factors in the exponent» of the chapter) we obtain
\[ T(|I|)=2^{\Theta(|I|)}: \]CountPairsis exponential in the input size. -
In the worst case (array in strictly decreasing order) line 8 is executed at every iteration of the inner loop. For a fixed \(i\), the inner loop executes \(n-i\) iterations, for a total of \(\sum_{i=1}^{n-1}(n-i)=\frac{n(n-1)}{2}\). The number of times each line is executed is:
-
Line 4 is executed \(n\) times
-
Line 6 is executed \(\frac{n(n-1)}{2}+(n-1)\) times
-
Lines 7, 8 and 10 are executed \(\frac{n(n-1)}{2}\) times each
Therefore
\[ S(n)=3+n+3(n-1)+4\cdot\frac{n(n-1)}{2}=2n^2+2n=\Theta(n^2). \]The input is an array, so \(|I|=\Omega(n)\), i.e., \(n\le\frac1c|I|\), and
\[ S(n)\le a\,n^2\le\frac{a}{c^2}|I|^2 \quad\Longrightarrow\quad T(|I|)=O(|I|^2). \]If every entry uses at most \(c\) bits, with \(c\) a constant, then \(|I|=\Theta(n)\), and more precisely \(n\ge\frac1c|I|\). For a lower bound, note that only line 8 depends on the values: even if it is never executed, the algorithm executes
\[ 2n^2+2n-\frac{n(n-1)}{2}=\frac{3n^2+5n}{2}\ge\frac32\,n^2\ge\frac{3}{2c^2}\,|I|^2 \]steps. Every input of size \(|I|\) requires at least this number of steps, so \(T(|I|)=\Omega(|I|^2)\) and, together with the upper bound,
\[ T(|I|)=\Theta(|I|^2). \]In both cases
CountInversionsis polynomial (quadratic). -
The number of steps is the same function of \(n\), but \(n\) has a different relation with the input size:
-
in
CountPairs, \(n\) is the value of the input, which is written with only \(\Theta(\log_2 n)\) bits, so \(n=2^{\Theta(|I|)}\); -
in
CountInversions, \(n\) is the number of entries of the array, and each entry needs at least one bit, so \(n=O(|I|)\).
The same \(S(n)\) can correspond to a polynomial or to an exponential running time: it depends on how the parameter \(n\) is related to the input size \(|I|\).
-
-
The bits of \(n=5\) are \(\lfloor\log_2 5\rfloor+1=3\), and the bits of the array are \(3+2+3+1+2=11\), so
\[ |I|=3+11=14. \]In general \(|I|=(\lfloor\log_2 n\rfloor+1)+\sum_{i=1}^{n}(\lfloor\log_2 a[i]\rfloor+1)\ge n\), so still \(|I|=\Omega(n)\) and \(T(|I|)=O(|I|^2)\). With entries of constant size, \(|I|=\Theta(\log_2 n)+\Theta(n)=\Theta(n)\), so \(T(|I|)=\Theta(|I|^2)\) as before: adding \(n\) to the input adds only \(\Theta(\log_2 n)\) bits, which is negligible with respect to the \(\Omega(n)\) bits of the array.