0
$\begingroup$

Can you find the function that satisfy the relation?

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

New contributor
Sonya is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
  • $\begingroup$ Can you update the question adding some hints on what have you tried? $\endgroup$ – Yamar69 Oct 9 at 11:07
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Leo163 Oct 9 at 11:54
  • 1
    $\begingroup$ The essence of your comments remains valid anyway. $\endgroup$ – Leo163 Oct 9 at 11:54
  • $\begingroup$ @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. $\endgroup$ – OmG Oct 9 at 12:51
  • 2
    $\begingroup$ 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. $\endgroup$ – Leo163 Oct 9 at 14:26

Your Answer

Sonya is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.