$f(n)$ belongs to $\Theta(g(n))$ then it implies that $2^{f(n)}$ belongs to $\Theta(2^{g(n)})$. [True]
$f(n)$ does not belong to $o(g(n))$ and $f(n)$ does not belong to $\omega(g(n))$ then it implies that $f(n)$ belongs to $\Theta(g(n))$- [true]
$f(n)$ belongs to $\mathcal{O}(g(n))$ implies that $g(n)$ belongs to $\mathcal{O}(g(n)+f(n))$ - [cannot prove it]
$a^n=\Theta(b^n)$ , where $b>a$ - [true]
$o(g(n))\cap\omega(g(n)) = \emptyset$ -[ false]
Asked
Active
Viewed 129 times
0
girl101
- 333
-
- is false, take $f(n) = n$ and $g(n) = 2n$. Then $2^{f(n)} = 2^n$ is not in $\Theta(2^{g(n)}) = \Theta(4^n)$.
– Antonio Vargas Nov 27 '14 at 19:24
1 Answers
0
- Correct
- Correct
- Assuming the functions are $\mathbb N \rightarrow \mathbb N$, meaning $f(n)>0$ then $g(n)\leq g(n)+f(n)=1\cdot (g(n)+f(n)) \longrightarrow g(n)\in O(g(n)+f(n))$. If they are not positive, you can find a counterexample.
- Incorrect. Assume correctness in contratiction. Then $a^n \in \Omega (b^n)$. Then exists $c>0$ s.t. $b^n\leq c\cdot a^n$. Then $(\frac{b}{a})^n\leq c$. But since $b>a$ for large enough $n_0$ (you can find it easily) this $(\frac{b}{a})^{n_0}>c $.
- Incorrect. This is true. $f\in o(g)$ only if $\lim_{n\rightarrow \infty}{\frac{f(n)}{g(n)}}=0$ and $f\in \omega (g)$ only if $\lim_{n\rightarrow \infty}{\frac{f(n)}{g(n)}}=\infty$. But $0\neq \infty$...
nitzpo
- 257
-
- is false, take $f(n) = n$ and $g(n) = 2n$. Then $2^{f(n)} = 2^n$ is not in $\Theta(2^{g(n)}) = \Theta(4^n)$.
– Antonio Vargas Nov 27 '14 at 19:26