As an exercise, we have to prove or disprove certain statements about the properties of Big O Notation.
I struggle with two of those right now.
- "For all $a,b \in N, a \le b: n^{\frac{1}{a}} \in \Theta(n^{\frac{1}{b}})$."
Is the first one correct? I have to prove that:
$c*n^{\frac{1}{b}} \le n^{\frac{1}{a}} \le s*n^{\frac{1}{b}} $
holds true for every every a and b. I think that you can always find a c small and a s big enough.. but how do I prove it?
- "There are different functions f and g, so that $f \in \Omega(g)$ and $g \in \Omega(f)$."
The second one is true, right? Essentially I have to prove that for $f(n) \neq g(n)$ that
$c*g(n)\le f(n)$ and $s*f(n) \le g(n)$
holds for some functions true, so I have to find just one and I proved it. I'd say for example $f(n)=n^2+1$ and $g(n)=n^2$. So $c=1$ and $s=\frac{1}{2}$ for example.
Thanks for the help!