Asymptotic notation problems, am i correct??

130 Views Asked by At
  1. $f(n)$ belongs to $\Theta(g(n))$ then it implies that $2^{f(n)}$ belongs to $\Theta(2^{g(n)})$. [True]

  2. $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]

  3. $f(n)$ belongs to $\mathcal{O}(g(n))$ implies that $g(n)$ belongs to $\mathcal{O}(g(n)+f(n))$ - [cannot prove it]

  4. $a^n=\Theta(b^n)$ , where $b>a$ - [true]

  5. $o(g(n))\cap\omega(g(n)) = \emptyset$ -[ false]

1

There are 1 best solutions below

1
On BEST ANSWER
  1. Correct
  2. Correct
  3. 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.
  4. 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 $.
  5. 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$...