if $f(n)=\Theta (\Theta(g(n)))$, then $f(n)=\Theta g(n)$

39 Views Asked by At

Please correct me if I am wrong. Suppose $h(n)=\Theta (g(n))$

  1. $f(n)=\Theta(\Theta (g(n)))$
  2. $f(n)=O(\Theta (g(n)))$ and $f(n)=\Omega(\Theta (g(n)))$
  3. $\exists c_1\in R(f(n)\leq c_1\theta(g(n))),\exists c_2\in R(f(n)\geq c_2\theta(g(n)))$
  4. $c_2\Theta(g(n))\leq f(n)\leq c_1\Theta(g(n))$
  5. $c_2(h(n))\leq f(n)\leq c_1(h(n))$
  6. $\exists c_3,c_4\in R(c_4(g(n))\leq c_2(h(n))\leq f(n)\leq c_1(h(n))\leq c_3(g(n))$
  7. $f(n)=O(g(n))$ and $f(n)=\Omega(g(n))$
  8. $f(n)=\Theta(g(n))$

Now, my questions are

  1. Am I doing these correct?
  2. Also, WLOG, I know the necessary condition of $n\ge n_0$. But I simply left it to save the trouble. Will this affect my proof?