若f(n) = O(n)，g(n) = O(n)，证明f(g(n)) = O(n)

Question

我似乎想不出如何解决这个问题。大O把我搞糊涂了。有人能帮我弄清楚吗？f(n) = O(n)和g(n) = O(n)。我如何证明f(g(n)) = O(n)

Answer 1

使用O定义：

f(n) = O(n) => f(n) < c1*n for n > n0 and c1 is constant.
g(n) = O(n) => g(n) < c2*n for n > n1 and c2 is constant.

因此，我们有：

f(g(n)) < c1 * g(n) < c1 * c2 * n for n > max(n0, n1) => 
f(g(n)) < c3 * n for n > max(n0, n1) and c3 is constant.

后者是O的定义，意思是f(g(n)) = O(n)。