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?
Big-O and not little-o implies theta?
asymptotics;landau notation
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.