4

I'm looking for a simple example function, f(n), that is Big-O of some other function, g(n), but is not Little-o of g(n). In other words, some f(n) such that f(n) is O(g(n)), but not o(g(n)).

The simplest case I can think of is f(n) = n, g(n) = n. f(n) is clearly O(g(n)). We learned in class that one definition of little-o notation is whether f(n)/g(n) as n --> infinity, goes to 0. In this case, f(n)/g(n) as n goes to infinity approaches 1, therefore f(n) is not o(g(n)).

Is this logic correct? Am I missing something?

kaya3
  • 47,440
  • 4
  • 68
  • 97
Jeffrey
  • 83
  • 5
  • 2
    I'm so happy seeing proper usage of little-o in a coding context. Usually when I see it, it's people who mean Big-O but just can't be bothered to hold the shift key. Drives me nuts. – Kelly Bundy Feb 06 '20 at 05:47

1 Answers1

4

Yes, your reasoning is correct, and your conclusion is correct.

Another way of thinking about this is that O(g) is the set of functions which don't grow asymptotically faster than g, and o(g) is the set of functions which grow asymptotically slower than g. So if f grows at the same asymptotic rate as g, then f is in O(g) but not o(g). The set o(g) is a subset of O(g), and the set difference O(g) \ o(g) = Θ(g).

As a pedant, I'm compelled to note that you asked for a "function, f(n), that is Big-O of some other function, g(n)" (emphasis mine), so you should choose a different function like g(n) = 2n for it to be some other function. ;-)

kaya3
  • 47,440
  • 4
  • 68
  • 97