Algorithms - Exercises from Chapter 0

1. In each of the following situations, indicate whether \(f = \mathcal{O}(g)\) (or) \(f = \Omega(g)\) or both (in which case \(f = \Theta(g)\)).
• \(n-100 = \Theta(n-200)\)
• \(n^{1/2} = \mathcal{O}(n^{2/3})\)
• \(100n + \log n = \mathcal{O}(n + (\log n)^2)\)
• \(n \log n = \Theta (10n \log 10n)\)
• \(\log 2n = \Theta (\log 3n)\)
• \(10 \log n = \Theta (\log \left( n^2 \right))\)
• \(n^{1.01} = \Omega (n \log^2 n)\)
• \(n^2 / \log n = \mathcal{O}(n (\log n)^2)\)
• \(n^{0.1} = \mathcal{O}(\left( \log n \right)^{10})\)
• \((\log n)^{\log n} = \Omega(n / \log n\))
• \(\sqrt{n} = \Omega ((\log n)^3)\)
• \(n^{1/2} = \mathcal{O}(5^{\log_2n})\)
• \(n2^n = \mathcal{O}(3^n)\)
• \(2^n = \Theta (2^{n+1})\)
• \(n! = \Omega (2^n)\)
• \(\left(\log n \right)^{\log n} = 2^{\left(\log_2 n \right)^2}\)
• \(\sum_{i=1}^{n} i^k = \Theta (n^{k+1})\)
2. Show that, if \(c\) is a positive real number, then \(g(n) = 1 + c + c^2 + \cdots + c^n\) is:
• \(\Theta(1) \) if \(c \lt 1\)
• \(\Theta(n) \) if \(c = 1\)
• \(\Theta(c^n) \) if \(c \gt 1\)
• Solution: We have that \(g(n) = \frac{c^{n+1}-1}{c-1}\) whenever \(c \neq 1\). Note that \(g(n)\) is a monotonously increasing function for all positive real \(c\) i.e. we have \(g(n+1) \gt g(n)\).
• If \(c \lt 1\), we have \(1 \leq g(n) \lt \frac1{1-c}\), for all \(n \in \mathbb{Z}^+\). Hence, we get \(g(n) = \Theta(1)\).
• If \(c = 1\), we have \(g(n) = n+1\). Hence, we have that \(g(n) = \Theta(n)\).
• Since \(c \in \mathbb{R}^+\), we have \(g(n) \gt c^n, \forall n \in \mathbb{Z}^+\). For \(c \gt 1\), choose \(k = \frac{c}{c-1}\). We have \(1 + c + c^2 + \cdots + c^n =\frac{c^{n+1}-1}{c-1} \lt \frac{c^{n+1}}{c-1} = \frac{c}{c-1} c^n = k c^n\). Hence, we have for any \(n\), \[c^n \lt 1 + c + c^2 + \cdots + c^n \lt k c^n.\] Hence, we get \(g(n) = \Theta(c^n)\).
3. The Fibonacci numbers are defined by the rule \[F_0 = 0, F_1 = 1, F_{n} = F_{n-1} + F_{n-2}, n \geq 2.\] In this problem, we will confirm that this sequence grows exponentially fast and obtain some bounds on its growth.
• Use induction to prove that \(F_n \geq 2^{0.5n}\) for \(n \geq 6\).
• We have \(F_6 = 8 = 2^{0.5 \times 6}\) and \(F_7 = 13 \gt 12 \gt 8 \times 1.5 \gt 8 \times \sqrt{2} = 2^{3.5}\). Assume that for all \(k\) such that \(6 \leq k \leq m\), we have \(F_k \geq 2^{0.5k}\). We have \(F_{m+1} = F_{m} + F_{m-1} \gt 2^{0.5 m} + 2 ^{0.5 (m-1)} = 2 ^{0.5 m} \left(1 + \frac1{\sqrt{2}} \right) \gt 2^{0.5 m} \sqrt{2} = 2^{0.5 (m+1)}.\) We have checked the base cases for \(k=6\) and \(k=7\) and hence by induction we have \(F_n \geq 2^{0.5n}\). Hence proved.
• Find a constant \(c \lt 1\) such that \(F_n \leq 2^{cn}\) for all \(n \geq 0\). Show that the answer is correct.
• We need \(2^{c(n+1)} \geq 2^{cn} + 2^{c(n-1)}\) i.e. we need \(2^c \geq 1 + \frac1{2^c}\). Setting \(2^c = x\), we need \(x\) such that \(x \geq 1 + \frac1x\) i.e. we need \(x\) such that \(x^2 \geq x + 1\). Since we have \(x = 2^c\) and \(0 \leq c \lt 1\), we need \(x\) such that \(1 \leq x \lt 2\). Setting \(x^2 - x - 1 = 0\), we get \(x = \frac{1 \pm \sqrt{5}}{2}\). Since \(1 \leq x \lt 2\), we get \(x = \frac{1 + \sqrt{5}}{2}\). Hence, set \(c = \log_2 \left(\frac{1 + \sqrt{5}}{2}\right)\). We shall now check that setting \(c = \log_2 \left(\frac{1 + \sqrt{5}}{2}\right)\), we have \(F_n \leq 2^{cn}\). Clearly, we have \(F_0 = 0 \lt 1 = 2^{c \times 0}\). Similarly, we have \(F_1 = 1 \lt \frac{1 + \sqrt{5}}{2} = 2^{\log_2 \left(\frac{1 + \sqrt{5}}{2}\right)}\). Assume that we have \(F_k \leq 2^{ck}\) for all \(k \leq m\). Hence, we get \(F_{m+1} = F_m + F_{m-1} \leq 2^{cm} + 2^{c(m-1)} = 2^{cm} \left(1 + \frac1{2^c} \right) = 2^{cm + c} = 2^{c(m+1)}\). Hence, \(c = \log_2 \left(\frac{1+\sqrt{5}}{2} \right)\) does the job.
• What is the largest \(c\) you can find for which \(F_n = \Omega (2^{cn})\)?
• By a similar argument as above, we get that \(c = \log_2 \left(\frac{1+\sqrt{5}}{2} \right)\) does the job.
4. Is there a faster way to compute the \(n^{th}\) Fibonacci number? One idea involves \(matrices\). We start by writing the equations \(F_1 = F_1\) and \(F_2 = F_0 + F_1\) in matrix notation: \[ \begin{pmatrix}F_1 \\ F_2 \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} \begin{pmatrix}F_0 \\ F_1 \end{pmatrix}\] Similarly, \[\begin{pmatrix}F_2 \\ F_3 \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} \begin{pmatrix}F_1 \\ F_2 \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^2 \begin{pmatrix}F_0 \\ F_1 \end{pmatrix}\] and in general, we have \[\begin{pmatrix} F_n \\ F_{n+1} \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^n \begin{pmatrix}F_0 \\ F_1 \end{pmatrix}\] So, in order to compute \(F_n\), it suffices to raise this \(2 \times 2\) matrix, call it \(X\), to the \(n^{th}\) power.
• Show that two \(2 \times 2\) matrices can be multiplied using \(4\) additions and \(8\) multiplications.
• \[\begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix} e & f \\ g & h \end{pmatrix} = \begin{pmatrix} a \times e + b \times g & a \times f + b \times h \\ c \times e + d \times g & c \times f + d \times h \end{pmatrix}\] Hence, it is clear that we need \(4\) additions and \(8\) multiplications.