2

In other words, is o(f(n)) = O(f(n)) - Θ(f(n))?

f ∈ O(g) [big O] says, essentially

For at least one choice of a constant k > 0, you can find a constant y such that the inequality 0 <= f(x) <= k g(x) holds for all x > y.

f ∈ Θ(g) [theta] says, essentially

For at least one choice of constants k1, k2 > 0, you can find a constant y such that the inequality 0 <= k1 g(x) <= f(x) <= k2 g(x) holds for all x > y.

f ∈ o(g) [little o] says, essentially

For every choice of a constant k > 0, you can find a constant a such that the inequality 0 <= f(x) < k g(x) holds for all x > y.

By the definition, it is easy to realize that o(g) ⊆ O(g), and Θ(g) ⊆ O(g). And it makes sense to one complement each other. I couldn't find any counter example of function that is in O(f(n)) and not in Θ(f(n)) that is not in o(f(n)).

Luis Grappi
  • 87
  • 2
  • 8

1 Answers1

2

Surprisingly, no, this isn’t the case. Intuitively, big-O notation gives an upper bound without making any claims about lower bounds. If you subtract out the big-Θ class, you’ve removed functions that are bounded from above and below by the function. That leaves you with some extra functions that are upper-bounded by the function but not lower bounded by it.

As an example, let f(n) be n if n is even and 0 otherwise. Then f(n) = O(n) but f(n) ≠ Θ(n). However, it’s not true that f(n) = o(n).

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • Hmmm, that's true! Thanks for pointing, I forgot about this kind of functions. But, to be more specific to what I want to understand, the statement that I made in the question is valid for **polynomial functions**? If so, can we prove it? Otherwise, do we have a counter example? – Luis Grappi Aug 31 '22 at 02:10
  • 1
    Polynomials are very “well-behaved” functions. Any polynomial is Theta of n to its degree, which greatly simplifies things. You can use that to prove, for example, that p(n) = O(q(n)) if and only if the degree of p is at most the degree of q, for example. From there, proving the claim from your original question becomes a lot easier (and it’s true if you’re only looking at polynomials). – templatetypedef Aug 31 '22 at 02:16