proving these assertions

35 Views Asked by At

The assertion is the following $f(n) \in O(n) \rightarrow f(n)^2 \in O(n^2)$ Here is my idea since $f(n) \in O(n)$ then $\exists c > 0 : f(n) \leq cn $ thus $f(n)^2 \leq c^2 n^2 \iff f(n)^2 \in O(n^2)$ correct? the second one is $f(n) \in O(n) \rightarrow 2^{f(n)} \in O(2^n)$ Here is my idea since $f(n) \in O(n)$ then $\exists c > 0 : f(n) \leq cn \iff 2^{f(n)} \leq 2^{cn} = 2^c \cdot 2^n = \lambda 2^n \iff 2^{f(n)} \in O(2^n)$ Valid too?