Question

(a) Suppose f and g are functions whose domains are subsets of z+, the set of positive integers. Give the definition of 'f is $\Omicron$(g)'

(b) Use the definition of 'f is $\Omicron$(g)' to show that:

(I) 2ⁿ+27 is $\Omicron$(3ⁿ)

(ii) 5ⁿ is not $\Omicron$(4ⁿ)

Answer 1

Let $f$ and $g$ are functions whose domains are subsets of $\Z_+$, the set of positive integers. We say that $f$ is $O(g)$ if there exist a positive real number $c$ and a positive integer $n_0$ such that $f(n)\le cg(n)$ for all $n\ge n_0.$

(b) Let us use the definition of 'f is $\Omicron$(g)' to show that the following statements.

(I) Since $2^n+27<3^n+27\cdot 3^n=28\cdot 3^n$ for each positive integer $n,$ we put $c=28$ and conclude that $2^n+27$ is $O(3^n).$

(ii) Let us show that $5^n$ is not $O(4^n).$ Let us prove using the method by contradiction. Suppose that there exist a positive real number $c$ and a positive integer $n_0$ such that $5^n\le c\cdot 4^n$ for all $n\ge n_0.$

It follows that $(\frac{5}{4})^n\le c$ for all $n\ge n_0.$ Since $\lim\limits_{n\to+\infty}(\frac{5}{4})^n=+\infty,$ we conclude that there exist $m\in\Z_+$ such that $(\frac{5}{4})^n>c$ for all $n\ge m.$ This contradiction proves the statement.