Question

Determine whether each of the functions \({2^{n + 1}}\)and \({2^{2n}}\)is \(O({2^n})\).

Short answer

We have determined that the function \(f(n) = {2^{n + 1}}\) is \(O({2^n})\)and \(g(n) = {2^n}\) is not \(O({2^n})\).

Step-by-step solution

Step 1:

Using \(f(n) = {2^{n + 1}}\) and \(g(n) = {2^n}\), we get that,

\(\begin{array}{l}f(n) = {2^{n + 1}}\\ \Rightarrow f(n) = {2.2^n}\\ \Rightarrow f(n) = 2g(n)\end{array}\)

By using \(f(n) = 2g(n)\) and the definition of Big -O Notation that is

\(|f(x)| \le C|g(x)|\), we can conclude that function \(f(n) = {2^{n + 1}}\) is \(O({2^n})\) with \(C = 1{\rm{ and }}k = 1\).

Step 2:

Using \(f(n) = {2^{2n}}\) and \(g(n) = {2^n}\), we get that

\(\begin{array}{l}f(n) = {2^{2n}}\\ \Rightarrow f(n) = {4^n}\end{array}\)

Comparing this with \(g(n) = {2^n}\), we get that

\(f(n) > g(n)\).

Step 3:

By using \(f(n) > g(n)\) and the definition of Big-O Notation that is

\(|f(x)| \le C|g(x)|\), we can imply that function \({2^{2n}}\)is not \(O({2^n})\).

We have determined that the function \(f(n) = {2^{n + 1}}\) is \(O({2^n})\)and \(g(n) = {2^n}\) is not \(O({2^n})\).