Interactive · 1 question

The definition of o(f(x))o(f(x)) implies that if f(x)<g(x)f(x) < g(x), then o(f(x))⊆o(g(x))o(f(x)) \subseteq o(g(x)): given a function h(x)∈o(f(x))h(x) \in o(f(x)), eventually ∣h(x)∣<ϵ⋅f(x)|h(x)| < \epsilon \cdot f(x) for any ϵ\epsilon, but then ∣h(x)∣<ϵ⋅g(x)|h(x)| < \epsilon \cdot g(x) as well.

This makes intuitive sense: if h(x)h(x) is insignificantly small compared to f(x)f(x), then it's insignificantly small compared to larger functions as well.

However, as we'll see, sometimes o(f(x))o(f(x)) and o(g(x))o(g(x)) are the same even if f(x)<g(x)f(x) < g(x) for all xx.

Different ways to write o(f(x))o(f(x))

By our definition, o(x2)o(x^2) is the set of functions f(x)f(x) that eventually become much smaller than x2x^2: for any ϵ>0\epsilon > 0, we have ∣f(x)∣<ϵ⋅x2|f(x)| < \epsilon \cdot x^2 whenever xx is large enough.

What about o(10x2)o(10x^2)? The definition is the same, except that we want ∣f(x)∣<ϵ⋅10x2=10ϵ⋅x2|f(x)| < \epsilon \cdot 10x^2 = 10\epsilon \cdot x^2 to hold, instead. This makes the threshold ϵ\epsilon weaker: using ϵ=0.01\epsilon = 0.01 relative to 10x210x^2, for instance, is the same as using ϵ=0.1\epsilon = 0.1 relative to x2x^2.

But the bound ∣f(x)∣<ϵ⋅x2|f(x)| < \epsilon \cdot x^2 has to hold for any ϵ\epsilon we pick! If f(x)∈o(10x2)f(x) \in o(10x^2), then we still know that eventually we'll have ∣f(x)∣<0.01x2|f(x)| < 0.01 x^2; we just have to pick ϵ=0.001\epsilon = 0.001 instead of ϵ=0.01\epsilon=0.01. This means that o(10x2)o(10x^2) and o(x2)o(x^2) are just different ways of describing the same set.

More is true. Writing o(x2+100x)o(x^2 + 100x) would also describe the same set: since 100x∈o(x2)100x \in o(x^2), eventually x2+100xx^2 + 100x becomes less than x2+x2x^2 + x^2, and o(x2)=o(2x2)o(x^2) = o(2x^2).

Comparing o(f(x))o(f(x)) and o(g(x))o(g(x))

In general, to have o(f(x))⊆o(g(x))o(f(x)) \subseteq o(g(x)), we don't need to have f(x)<g(x)f(x) < g(x). All that we need is that for some (possibly large) constant CC, we eventually have f(x)<C⋅g(x)f(x) < C\cdot g(x).

Intuitively, since we can make our thresholds arbitrarily small, we don't care about constant factors. And since we only care about large values of xx, we don't care about how f(x)f(x) and g(x)g(x) compare for small xx.

How do the classes below compare to o(x2)o(x^2)?

Choose all correct answers

Type a concept, like “slope” or “photosynthesis”.

↑ ↓ to choose · Enter to openSearch explanations and problems