3-4 Asymptotic notation properties

Let $f(n)$ and $g(n)$ by asymptotically positive functions. Prove or disprove each of the following conjectures.

a. $f(n)=O(g(n))$ implies $g(n)=O(f(n))$.

b. $f(n)+g(n)=\mathrm{\Theta }(min(f(n),g(n)))$.

c. $f(n)=O(g(n))$ implies $\lg (f(n))=O(\lg (g(n)))$, where $\lg (g(n))\ge 1$ and $f(n)\ge 1$ for all sufficiently large $n$.

d. $f(n)=O(g(n))$ implies $2^{f(n)}=O(2^{g(n)})$.

e. $f(n)=O((f(n){)}^2)$.

f. $f(n)=O(g(n))$ implies $g(n)=\mathrm{\Omega }(f(n))$.

g. $f(n)=\mathrm{\Theta }(f(n/2))$.

h. $f(n)+o(f(n))=\mathrm{\Theta }(f(n))$.

a. Disprove, $n=O(n^2)$, but $n^2\ne O(n)$.

b. Disprove, $n^2+n\ne \mathrm{\Theta }(min(n^2,n))=\mathrm{\Theta }(n)$.

c. Prove, because $f(n)\ge 1$ after a certain $n\ge n_0$.

We need to prove that

We can find $d$,

where the last step is valid, because $\lg g(n)\ge 1$.

d. Disprove, because $2n=O(n)$, but $2^{2n}=4^n\ne O(2^n)$.

e. Prove, $0\le f(n)\le c{f}^2(n)$ is trivial when $f(n)\ge 1$, but if $f(n)<1$ for all $n$, it's not correct. However, we don't care this case.

f. Prove, from the first, we know that $0\le f(n)\le cg(n)$ and we need to prove that $0\le df(n)\le g(n)$, which is straightforward with $d=1/c$.

g. Disprove, let's pick $f(n)=2^n$. We will need to prove that

which is obviously untrue.

h. Prove, let $g(n)=o(f(n))$. Then

We need to prove that

Thus, if we pick $c_1=1$ and $c_2=c+1$, it holds.

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用