Question

Show that \({2^n}\) is \(O({3^n})\) and \({3^n}\)is not \(O({2^n})\).

Short answer

Hence, we obtain\({2^n}\) is \(O({3^n})\) and \({3^n}\)is not \(O({2^n})\).

Step-by-step solution

Step 1:

Let \(f(x) = {2^n}\) and \(g(x) = {3^n}\)

When \(x > 1\)we have property \({3^n} > {2^n}\)

Let \(k = 1\)

\(\left| {f(x)} \right| = \left| {{2^n}} \right| \le \left| {{3^n}} \right|\)

\( \Rightarrow C = 1\)

\( \Rightarrow f(x) = {2^n}\) is \(O({3^n})\)

Step 2:

Let \(f(x) = {3^n}\) and \(g(x) = {2^n}\)

Assuming \(f(x) = {3^n}\)is\(O({2^n})\).

\( \Rightarrow \left| {{3^n}} \right| \le C\left| {{2^n}} \right|\)where \(n > k\)

Let\(k > 1\)

\(\begin{array}{l}{3^n} = \left| {{3^n}} \right| \le C\left| {{2^n}} \right|\\ = C{2^n}\end{array}\)

Solving inequality

\(\begin{array}{l}C \le \frac{{{3^n}}}{{{2^n}}}\\C \le {\left( {\frac{3}{2}} \right)^n}\end{array}\)

Now,\(n \le {\log _{3/2}}(C)\)

Here, we are getting a contradiction because\(n > k\)

\( \Rightarrow \)\(f(x) = {3^n}\)is not \(O({2^n})\)