# Find function that satisfy the relation

Can you find the function that satisfy the relation?

$$f(n) = \Theta(g(n)), f(n) = o(g(n))$$

• Can you update the question adding some hints on what have you tried? – Yamar69 Oct 9 '19 at 11:07

If oh is little, it is not possible. Because of the definition of these two symbols. $$f(n) = \Theta(g(n))$$ means there is two constants $$c_1, c_2 > 0$$ and $$n_0 \in \mathbb{N}$$ such that $$g(n) < c_1 f(n)$$ and $$f(n) < c_2 g(n)$$ for $$n > n_0$$. Hence, it means $$\lim_{n\to \infty} \frac{f(n)}{g(n)} = constant > 0$$.
However, the definition of the little-oh is $$\lim_{n\to\infty}\frac{f(n)}{g(n)} = 0$$ and there is not constant $$c$$ and $$n_1$$, such that $$g(n) < c f(n)$$ for $$n > n_1$$.
Also, if you mean big-oh, by the definition, you can say if $$f(n) = \Theta(g(n))$$, you can always say $$f(n) = O(g(n))$$ too.
• There is something strange with your definition of $\Theta$: e.g. if $f=1$ and $g=(1/2)^{(-1)^n}$, then $\lim_{n\to\infty} f/g$ does not exists, although you can find constants $c_1$ and $c_2$ as you describe above. – Leo163 Oct 9 '19 at 11:54
• @Leo163 you're right. But as a matter of complexity, I assume that $f(n)$ and $g(n)$ are functions in natural numbers and positive. – OmG Oct 9 '19 at 12:51
• Even with these assumptions there is a problem: just take $f$ as above and let $g'$ be $2g$: they are both function with $\mathbb{Z}^+$ as range, but the issue of nonexistence of the limit exists. – Leo163 Oct 9 '19 at 14:26