Big-O and not little-o implies theta?

Question

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?

Answer 1

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.

Answer 2

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))$.