Interactive · 1 question
The definition of implies that if , then : given a function , eventually for any , but then as well.
This makes intuitive sense: if is insignificantly small compared to , then it's insignificantly small compared to larger functions as well.
However, as we'll see, sometimes and are the same even if for all .
Different ways to write
By our definition, is the set of functions that eventually become much smaller than : for any , we have whenever is large enough.
What about ? The definition is the same, except that we want to hold, instead. This makes the threshold weaker: using relative to , for instance, is the same as using relative to .
But the bound has to hold for any we pick! If , then we still know that eventually we'll have ; we just have to pick instead of . This means that and are just different ways of describing the same set.
More is true. Writing would also describe the same set: since , eventually becomes less than , and .
Comparing and
In general, to have , we don't need to have . All that we need is that for some (possibly large) constant , we eventually have .
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 , we don't care about how and compare for small .
How do the classes below compare to ?