2.31

(a) no.  Because [math]\dfrac{3^{n}}{2^{n}}=\bigl(\tfrac{3}{2}\bigr)^{n}\!\to\infty[/math], no constant [math]c[/math] can satisfy [math]3^{n}\le c\,2^{n}[/math] for all large [math]n[/math].
(b) yes.  [math]\log 3^{n}=n\log 3=\dfrac{\log 3}{\log 2}\,n\log 2=\dfrac{\log 3}{\log 2}\,\log 2^{n}[/math]; the factor [math]\log 3/\log 2[/math] is a positive constant, so the Big-O bound holds.
(c) yes.  Since [math]3^{n}=2^{n}\bigl(\tfrac{3}{2}\bigr)^{n}[/math] and [math]\bigl(\tfrac{3}{2}\bigr)^{n}\!\ge 1[/math] for all [math]n\ge 0[/math], we have [math]3^{n}\ge 2^{n}[/math], i.e. [math]3^{n}=\Omega(2^{n})[/math].
(d) yes.  From (b), [math]\log 3^{n}=\dfrac{\log 3}{\log 2}\,\log 2^{n}[/math]; the same constant shows [math]\log 3^{n}=\Omega(\log 2^{n})[/math].

Back to Chapter 2