(a) Suppose f and g are functions whose domains are subsets of z+, the set of positive integers. Give the definition of 'f is \OmicronO(g)' (b) Use the definition of 'f is \OmicronO(g)' to show that: (I) 2n+27 is \OmicronO(3n) (ii) 5n is not \OmicronO(4n)

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.