Search for question
Question

3. (16 pts.) Assume you have positive functions f(n), g(n) and h(n) over positive integers n ≥ 1. For each of the following statements, decide if you think it is true or false and give a proof or counterexample. \text { 1. If } f(n)=O(g(n)) \text { and } g(n)=O(h(n)) \text {, then } f(n)=O(h(n)) \text {. } \text { 2. If } f(n)=\theta(g(n)) \text {, then } 2^{f(n)}=\theta\left(2^{g(n)}\right) \text {. } \text { 3. If } f(n)=o(g(n)) \text {, then } \log f(n)=o(\log g(n)) \text { 4. If } f(n)=O(g(n)) \text {, then } \frac{1}{f(n)}=\Omega\left(\frac{1}{g(n)}\right)

Fig: 1

Fig: 2

Fig: 3

Fig: 4

Fig: 5