Why is f=O(g) if f(n) grows more slowly than g(n)?

Question

If a function f(n) grows more slowly than a function g(n), why is f(n) = O(g(n))?

e.g. if f(n) is 4n^4 and g(n) is log(4n^n^4)
My book says f=O(g(n)) because g=n^4*log(4n)=n^4(logn + log4)=O(n^4*logn). I understand why g=O(n^4*logn), but I'm not sure how they reached the conclusion that f=O(g(n)) from big O of g.

I understand that f(n) grows more slowly than g(n) just by thinking about the graphs, but I'm having trouble understanding asymptotic behavior and why f=O(g(n)) in general.

Possible duplicate of [What is a plain English explanation of "Big O" notation?](http://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation) — Paul Hankin, Feb 23 '17 at 23:54
There is no asymptotic notation in the standard definition of big O. — Paul Hankin, Feb 23 '17 at 23:55
The function f(n) that you picked isn't O(g(n)). Did you write them backwards? — templatetypedef, Feb 23 '17 at 23:56
You might also want to look up the Omega and Theta classes that cover slower and equivalent growth. In your question you had probably Theta-like behavior in mind. — Lutz Lehmann, Feb 24 '17 at 15:33

score 2 · Answer 1 · answered Feb 24 '17 at 00:01

The formal definition of big-O notation is that

f(n) = O(g(n)) if there are constants n₀ and c such that for any n ≥ n₀, we have f(n) ≤ c · g(n).

In other words, f(n) = O(g(n)) if for sufficiently large values of n, the value of f(n) is upper-bounded by some constant multiple of g(n).

Notice that this just says that f(n) is upper-bounded by g(n), not that f(n)'s rate of growth is the same as g(n)'s rate of growth. In that sense, you can think of f(n) = O(g(n)) as akin to saying something like "f ≤ g," that f doesn't grow faster than g, leaving open the possibility that g grows a lot faster than f does.

Why is f=O(g) if f(n) grows more slowly than g(n)?

1 Answers1