Function in Big-O, but not in Little-O

Question

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?

Answer 1

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. ;-)