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.

Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani

This post contains the solution to the exercises of the book by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani named "Algorithms". This post is a work in progress.

1. Exercises in Chapter 0
2. Exercises in Chapter 1