Chapter 3

Show that: (a) \(f=o(g)\) implies \(f=O(g)\) and \(g \neq O(f)\); (b) \(f=O(g)\) and \(g=O(h)\) implies \(f=O(h)\) (c) \(f=O(g)\) and \(g=o(h)\) implies \(f=o(h)\) (d) \(f=o(g)\) and \(g=O(h)\) implies \(f=o(h)\).

Suppose \(f_{1}=O\left(g_{1}\right)\) and \(f_{2}=O\left(g_{2}\right) .\) Show that \(f_{1}+f_{2}=\) \(O\left(\max \left(g_{1}, g_{2}\right)\right), f_{1} f_{2}=O\left(g_{1} g_{2}\right),\) and that for every constant \(c, c f_{1}=O\left(g_{1}\right)\)

Suppose that \(f(x) \leq c+d g(x)\) for some positive constants \(c\) and \(d,\) and for all sufficiently large \(x .\) Show that if \(g=\Omega(1),\) then \(f=O(g)\).

Suppose \(f\) and \(g\) are defined on the integers \(i \geq k,\) and that \(g(i)>0\) for all \(i \geq k .\) Show that if \(f=O(g),\) then there exists a positive constant \(c\) such that \(|f(i)| \leq c g(i)\) for all \(i \geq k\)

Let \(f\) and \(g\) be eventually positive functions, and assume that \(f(x) / g(x)\) tends to a limit \(L\) (possibly \(L=\infty\) ) as \(x \rightarrow \infty\). Show that: (a) if \(L=0,\) then \(f=o(g)\); (b) if \(0

Let \(f(x):=x^{\alpha}(\log x)^{\beta}\) and \(g(x):=x^{\gamma}(\log x)^{\delta},\) where \(\alpha, \beta, \gamma, \delta\) are non-negative constants. Show that if \(\alpha<\gamma,\) or if \(\alpha=\gamma\) and \(\beta<\delta,\) then \(f=o(g)\)

Order the following functions in \(x\) so that for each adjacent pair \(f, g\) in the ordering, we have \(f=O(g),\) and indicate if \(f=o(g), f \sim g,\) or \(g=O(f)\) $$ \begin{array}{c} x^{3}, e^{x} x^{2}, 1 / x, x^{2}(x+100)+1 / x, x+\sqrt{x}, \log _{2} x, \log _{3} x, 2 x^{2}, x \\ e^{-x}, 2 x^{2}-10 x+4, e^{x+\sqrt{x}}, 2^{x}, 3^{x}, x^{-2}, x^{2}(\log x)^{1000} \end{array} $$

Show that: (a) the relation " \(\sim\) " is an equivalence relation on the set of eventually positive functions; (b) for all eventually positive functions \(f_{1}, f_{2}, g_{1}, g_{2},\) if \(f_{1} \sim g_{1}\) and \(f_{2} \sim g_{2},\) then \(f_{1} \star f_{2} \sim g_{1} \star g_{2},\) where " \(\star\) " denotes addition, multiplication, or division; (c) for all eventually positive functions \(f, g,\) and every \(\alpha>0,\) if \(f \sim g,\) then \(f^{\alpha} \sim g^{\alpha}\) (d) for all eventually positive functions \(f, g,\) and every function \(h\) such that \(h(x) \rightarrow \infty\) as \(x \rightarrow \infty,\) if \(f \sim g,\) then \(f \circ h \sim g \circ h,\) where "o" denotes function composition.

Let \(f, g\) be eventually positive functions. Show that: (a) \(f=\Theta(g)\) if and only if \(\log f=\log g+O(1)\); (b) \(f \sim g\) if and only if \(\log f=\log g+o(1)\).

Suppose that \(f\) and \(g\) are functions defined on the integers \(k, k+1, \ldots,\) and that \(g\) is eventually positive. For \(n \geq k,\) define \(F(n):=\sum_{i=k}^{n} f(i)\) and \(G(n):=\sum_{i=k}^{n} g(i) .\) Show that if \(f=O(g)\) and \(G\) is eventually positive, then \(F=O(G)\)

Suppose that \(f\) and \(g\) are piece-wise continuous on \([a, \infty)\) (see \(\S \mathrm{A} 4\) ), and that \(g\) is eventually positive. For \(x \geq a,\) define \(F(x):=\int_{a}^{x} f(t) d t\) and \(G(x):=\int_{a}^{x} g(t) d t .\) Show that if \(f=O(g)\) and \(G\) is eventually positive, then \(F=O(G)\)

Suppose that \(f\) and \(g\) are functions defined on the integers \(k, k+1, \ldots,\) and that both \(f\) and \(g\) are eventually positive. For \(n \geq k,\) define \(F(n):=\sum_{i=k}^{n} f(i)\) and \(G(n):=\sum_{i=k}^{n} g(i) .\) Show that if \(f \sim g\) and \(G(n) \rightarrow \infty\) as \(n \rightarrow \infty,\) then \(F \sim G\).

Suppose that \(f\) and \(g\) are piece-wise continuous on \([a, \infty)\) (see \$A4), and that both \(f\) and \(g\) are eventually positive. For \(x \geq a\), define \(F(x):=\) \(\int_{a}^{x} f(t) d t\) and \(G(x):=\int_{a}^{x} g(t) d t .\) Show that if \(f \sim g\) and \(G(x) \rightarrow \infty\) as \(x \rightarrow \infty\) then \(F \sim G\)

Work out the details of an algorithm that compares two signed integers \(a\) and \(b\), determining which of \(ab\) holds.

Work out the details for an algorithm that shifts a given unsigned integer \(a\) to the left by a specified number of bits \(s\) (i.e., computes \(b:=a \cdot 2^{s}\) ). The running time of your algorithm should be linear in the number of digits of the output.

Work out the details for an algorithm that shifts a given unsigned integer \(a\) to the right by a specified number of bits \(s\) (i.e., computes \(\left.b:=\left\lfloor a / 2^{s}\right\rfloor\right)\). The running time of your algorithm should be linear in the number of digits of the output. Now modify your algorithm so that it correctly computes \(\left\lfloor a / 2^{s}\right\rfloor\) for signed integers \(a\).

This exercise is for C/Java programmers. Evaluate the ClJava expressions $$ (-17) \% 4 ; \quad(-17) \& 3 ; $$ and compare these values with (-17) mod \(4 .\) Also evaluate the C/Java expressions $$ (-17) / 4 ; \quad(-17)>>2 ; $$ and compare with \(\lfloor-17 / 4\rfloor .\) Explain your findings.

This exercise is also for C/Java programmers. Suppose that values of type int are stored using a 32 -bit 2 's complement representation, and that all basic arithmetic operations are computed correctly modulo \(2^{32},\) even if an "overflow" happens to occur. Also assume that double precision floating point has 53 bits of precision, and that all basic arithmetic operations give a result with a relative error of at most \(2^{-53}\). Also assume that conversion from type int to double is exact, and that conversion from double to int truncates the fractional part. Now, suppose we are given int variables \(\mathrm{a}, \mathrm{b},\) and \(\mathrm{n},\) such that \(1<\mathrm{n}<2^{30}\), \(0 \leq a=\mathrm{n}) \\ \mathrm{r}=\mathrm{r}-\mathrm{n} \end{array} \\ \text { else if }(r<0) \\ \qquad r=r+\mathrm{n} \end{array} $$

Let \(a, b \in \mathbb{Z}\) with \(a \geq b>0,\) and let \(q:=\lfloor a / b\rfloor .\) Show that \(\operatorname{len}(a)-\operatorname{len}(b)-1 \leq \operatorname{len}(q) \leq \operatorname{len}(a)-\operatorname{len}(b)+1\)

Let \(n_{1}, \ldots, n_{k}\) be positive integers. Show that $$ \sum_{i=1}^{k} \operatorname{len}\left(n_{i}\right)-k \leq \operatorname{len}\left(\prod_{i=1}^{k} n_{i}\right) \leq \sum_{i=1}^{k} \operatorname{len}\left(n_{i}\right) $$

Show that given integers \(n_{1}, \ldots, n_{k},\) with each \(n_{i}>1,\) we can compute the product \(n:=\prod_{i} n_{i}\) in time \(O\left(\operatorname{len}(n)^{2}\right)\).

Show that given integers \(a, n_{1}, \ldots, n_{k},\) with each \(n_{i}>1,\) where \(0 \leq a

Show that given integers \(n_{1}, \ldots, n_{k},\) with each \(n_{i}>1,\) we can compute \(\left(n / n_{1}, \ldots, n / n_{k}\right),\) where \(n:=\prod_{i} n_{i},\) in time \(O\left(\operatorname{len}(n)^{2}\right) .\)

This exercise develops an algorithm to compute \(\lfloor\sqrt{n}\rfloor\) for a given positive integer \(n\). Consider the following algorithm: \(k \leftarrow\lfloor(\operatorname{len}(n)-1) / 2\rfloor, m \leftarrow 2^{k}\) for \(i \leftarrow k-1\) down to 0 do if \(\left(m+2^{i}\right)^{2} \leq n\) then \(m \leftarrow m+2^{i}\) output \(m\) (a) Show that this algorithm correctly computes \(\lfloor\sqrt{n}\rfloor\). (b) In a straightforward implementation of this algorithm, each loop iteration takes time \(O\left(\operatorname{len}(n)^{2}\right),\) yielding a total running time of \(O\left(\operatorname{len}(n)^{3}\right)\). Give a more careful implementation, so that each loop iteration takes time \(O(\operatorname{len}(n)),\) yielding a total running time is \(O\left(\operatorname{len}(n)^{2}\right) .\)

Show how to convert (in both directions) in time \(O\left(\operatorname{len}(n)^{2}\right)\) between the base-10 representation and our implementation's internal representation of an integer \(n\).

The repeated-squaring algorithm we have presented here processes the bits of the exponent from left to right (i.e., from high order to low order). Develop an algorithm for exponentiation in \(\mathbb{Z}_{n}\) with similar complexity that processes the bits of the exponent from right to left.

Show that given a prime \(p, \alpha \in \mathbb{Z}_{p},\) and an integer \(e \geq p,\) we can compute \(\alpha^{e}\) in time \(O\left(\operatorname{len}(e) \operatorname{len}(p)+\operatorname{len}(p)^{3}\right)\). The following exercises develop some important efficiency improvements to the basic repeated-squaring algorithm.

The goal of this exercise is to develop a "2 \(^{t}\) -ary" variant of the above repeated-squaring algorithm, in which the exponent is effectively treated as a number in base \(2^{t},\) for some parameter \(t,\) rather than in base \(2 .\) Let \(\alpha \in \mathbb{Z}_{n}\) and let \(e\) be a positive integer of length \(\ell\). Let us write \(e\) in base \(2^{t}\) as \(e=\left(e_{k} \cdots e_{0}\right)_{2^{t}}\), where \(e_{k} \neq 0 .\) Consider the following algorithm: compute a table of values \(T\left[0 \ldots 2^{t}-1\right]\), where \(T[j]:=\alpha^{j}\) for \(j=0, \ldots, 2^{t}-1\) \(\beta \leftarrow T\left[e_{k}\right]\) for \(i \leftarrow k-1\) down to 0 do $$ \beta \leftarrow \beta^{2^{t}} \cdot T\left[e_{i}\right] $$

Suppose we are given \(\alpha_{1}, \ldots, \alpha_{k} \in \mathbb{Z}_{n},\) along with non-negative integers \(e_{1}, \ldots, e_{k},\) where \(\operatorname{len}\left(e_{i}\right) \leq \ell\) for \(i=1, \ldots, k .\) Show how to compute \(\beta:=\alpha_{1}^{e_{1}} \cdots \alpha_{k}^{e_{k}},\) using at most \(\ell\) squarings and \(\ell+2^{k}\) additional multiplications in \(\mathbb{Z}_{n} .\) Your algorithm should work in two phases: the first phase uses only the values \(\alpha_{1}, \ldots, \alpha_{k},\) and performs at most \(2^{k}\) multiplications in \(\mathbb{Z}_{n} ;\) in the second phase, the algorithm computes \(\beta,\) using the exponents \(e_{1}, \ldots, e_{k},\) along with the data computed in the first phase, and performs at most \(\ell\) squarings and \(\ell\) additional multiplications in \(\mathbb{Z}_{n}\).

Suppose that we are to compute \(\alpha^{e}\), where \(\alpha \in \mathbb{Z}_{n},\) for many exponents \(e\) of length at most \(\ell,\) but with \(\alpha\) fixed. Show that for every positive integer parameter \(k,\) we can make a pre-computation (depending on \(\alpha, \ell,\) and \(k\) ) that uses at most \(\ell\) squarings and \(2^{k}\) additional multiplications in \(\mathbb{Z}_{n},\) so that after the pre-computation, we can compute \(\alpha^{e}\) for every exponent \(e\) of length at most \(\ell\) using at most \(\ell / k+O(1)\) squarings and \(\ell / k+O(1)\) additional multiplications in \(\mathbb{Z}_{n} .\)

Suppose we are given \(\alpha \in \mathbb{Z}_{n}\), along with integers \(m_{1}, \ldots, m_{r}\), with each \(m_{i}>1 .\) Let \(m:=\prod_{i} m_{i} .\) Also, for \(i=1, \ldots, r,\) let \(m_{i}^{*}:=m / m_{i}\) Show how to compute \(\left(\alpha^{m_{1}^{*}}, \ldots, \alpha^{m_{r}^{*}}\right)\) using \(O(\operatorname{len}(r) \ell)\) multiplications in \(\mathbb{Z}_{n},\) where \(\ell:=\operatorname{len}(m) .\) Hint: divide and conquer. Note that if \(r=O(\operatorname{len}(\ell)),\) then using the previous exercise, we can solve this problem using just \(O(\ell)\) multiplications.

Suppose we have two positive integers \(a\) and \(b\), each of length at most \(\ell,\) such that \(a=a_{1} 2^{k}+a_{0}\) and \(b=b_{1} 2^{k}+b_{0},\) where \(0 \leq a_{0}<2^{k}\) and \(0 \leq b_{0}<2^{k}\). Then $$ a b=a_{1} b_{1} 2^{2 k}+\left(a_{0} b_{1}+a_{1} b_{0}\right) 2^{k}+a_{0} b_{0} $$ Show how to compute the product \(a b\) in time \(O(\ell),\) given the products \(a_{0} b_{0}, a_{1} b_{1},\) and \(\left(a_{0}-a_{1}\right)\left(b_{0}-b_{1}\right) .\) From this, design a recursive algorithm that computes \(a b\) in time \(O\left(\ell^{\log _{2} 3}\right) .\) (Note that \(\left.\log _{2} 3 \approx 1.58 .\right)\) The algorithm in the previous exercise is also not the best possible. In fact, it is possible to multiply two integers of length at most \(\ell\) on a \(R A M\) in time \(O(\ell),\) but we do not explore this any further for the moment (see \(\$ 3.6\) ). The following exercises explore the relationship between integer multiplication and related problems. We assume that we have an algorithm that multiplies two integers of length at most \(\ell\) in time at most \(M(\ell) .\) It is convenient (and reasonable) to assume that \(M\) is a well-behaved complexity function. By this, we mean that \(M\) maps positive integers to positive real numbers, such that for some constant \(\gamma \geq 1,\) and all positive integers \(a\) and \(b,\) we have $$ 1 \leq \frac{M(a+b)}{M(a)+M(b)} \leq \gamma $$

Show that given integers \(n>1\) and \(e>1,\) we can compute \(n^{e}\) in time \(O\left(M\left(\operatorname{len}\left(n^{e}\right)\right)\right)\).

We can represent a "floating point" number \(\hat{z}\) as a pair \((a, e),\) where \(a\) and \(e\) are integers \(-\) the value of \(\hat{z}\) is the rational number \(a 2^{e},\) and we call len \((a)\) the precision of \(\hat{z} .\) We say that \(\hat{z}\) is a \(k\) -bit approximation of a real number \(z\) if \(\hat{z}\) has precision \(k\) and \(\hat{z}=(1+\varepsilon) z\) for some \(|\varepsilon| \leq 2^{-k+1}\). Show that given positive integers \(b\) and \(k,\) we can compute a \(k\) -bit approximation of \(1 / b\) in time \(O(M(k))\).

Suppose we have an algorithm that computes the square of an \(\ell\) -bit integer in time at most \(S(\ell),\) where \(S\) is a well-behaved complexity function. Show how to use this algorithm to compute the product of two arbitrary integers of length at most \(\ell\) in time \(O(S(\ell))\).