5
$\begingroup$

If $f(n)$ is in $O(g(n))$ but not in $o(g(n))$, is it true that $f(n)$ is in $\Theta(g(n))$?

Similarly, $f(n)$ is $\Omega(g(n))$ but not in $\omega(g(n))$ implies $f(n)$ is in $\Theta(g(n))$?

If not, can you provide an explanation/counter-example, please?

$\endgroup$
10
$\begingroup$

Let's start with the simple case $g = 1$, and $f$ having positive values only (that's all we care about with functions that represent complexity).

  • $f \in O(1)$ means that $f$ is bounded: there exists $B$ such that $f(n) \le B$ (for sufficiently large values of $n$).
  • $f \in o(1)$ means that $\lim_{n\to\infty} f(n) = 0$.
  • $f \in \Theta(1)$ means that $f$ is bounded above and below: there exists $A \gt 0$ and $B$ such that $A \le f(n) \le B$ (for sufficiently large values of $n$).

Note that $f \in \Theta(1)$ requires a positive (nonzero) lower bound for $f$: for sufficiently large $n$, $f(n) \ge A$. If $f \in o(1)$ then for sufficiently large $n$, $f(n) \lt A$. It is possible for neither of these to hold if $f$ oscillates between “large” (bounded below) and “small” (converging to zero) values, for example $$f(n) = \begin{cases} 1 & \text{if \(n\) is even} \\ 1/n & \text{if \(n\) is odd} \\ \end{cases}$$ Informally speaking, half of $f$ is $\Theta(1)$ (the even values) and half is $o(1)$ (the odd values), so $f$ is neither $\Theta(1)$ nor $o(1)$, despite being $O(1)$.

With $g = 1$, there are regularity conditions on $f$ that's sufficient to make $O$ and not $o$ imply $\Theta$: this does hold if $f$ is monotonic; more generally, it holds if $f$ has a limit at $\infty$. With arbitrary positive $g$, these sufficient conditions translate to conditions on the quotient $f/g$ being monotonic (because $f \in O(g)$ iff $f/g \in O(1)$, etc.). It isn't enough for $f$ and $g$ to be both increasing or any such condition from real analysis. You can take any $g$ and multiply it by the $f$ above to get a counterexample to your conjecture.

With algebraic conditions on $f$ and $g$, if they are taken from sufficiently restricted sets of functions, the conjecture may hold. For example, it holds if they're both polynomials (for polynomials, $f \in O(g)$ if $\deg(f) \le \deg(g)$, $f \in o(g)$ if $\deg(f) \lt \deg(g)$ and $f \in \Theta(g)$ if $\deg(f) = \deg(g)$). But as soon as you add “perturbations” to $f$ and $g$, all bets are off.

$\endgroup$
8
$\begingroup$

No, it isn't true. Just consider $f(n) = n \bmod 2$ and $g(n) = 1$.

We have $\forall n ~ f(n) \leq 1 \cdot g(n)$, so $f(n) \in O(g(n))$.

$\lim_{n \to \infty} f(n)/g(n)$ is undefined and therefore not $0$, so $f(n) \not\in o(g(n))$.

There is no positive number $a$ such that $f(n) \geq a \cdot g(n)$ for all $n$ starting with some $n_0$, so $f(n) \not\in \Omega(g(n))$ and therefore $f(n) \not\in \Theta(g(n))$.

$\endgroup$
  • $\begingroup$ I don't understand. Can't n mod 2 be bound by g(n) = 0 and g(n) = 1, thus being in Theta(g(n))? $\endgroup$ – Chara May 15 '16 at 6:55
  • 2
    $\begingroup$ It would need to be bounded by $a \cdot g(n)$ from below for some positive $a$, and it isn't. I expanded the answer a bit. $\endgroup$ – Alexey Romanov May 15 '16 at 7:09

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.