$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]
2026-04-04 19:11:05.1775329865
On
BEST ANSWER
Asymptotic notation problems, am i correct??
130 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
There are 1 best solutions below
1
On
BEST ANSWER
- 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$...