1
$\begingroup$

How to prove $\Theta(g(n))\cup o(g(n))\ne O(g(n))$ ?

Is there a simple example for understanding? Seems there's a gap between $O(g(n))- \Theta(g(n))$ and $o(g(n))$ just from the definition. But I cannot understand What kind of function lays there?

$\endgroup$
  • $\begingroup$ What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Sep 27 '18 at 16:10
  • $\begingroup$ Hint: Unfold the respective definitions and look for gaps. In particular, note the different kind of definition of $o$ compared to $O$! The usual tools for comparing functions by asymptotic growth may also be helpful. $\endgroup$ – Raphael Sep 27 '18 at 16:11
1
$\begingroup$

Consider the function $$ f(n) = \begin{cases} g(n) & \text{if $n$ is even}, \\ g(n)/n & \text{if $n$ is odd}. \end{cases} $$

$\endgroup$
1
$\begingroup$

$\Theta$ means "always roughly as big as". Little-o means "getting smaller and smaller compared to". Big-O means "always at most as big as" (all up to some constant).

Functions that are in O (g(n)) but neither in $\Theta (g(n))$ nor in o(g(n)) are those that vary between being as large as g(n) up to a constant and being arbitrary small compared to g(n). That's what Yuval's example does; it is often as large as g(n) but sometimes arbitrarily small compared to g(n). Both infinitely many times.

$\endgroup$

Your Answer

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.