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

要证明 f(g(n)) = O(n)，我们需要证明存在一个正常数 c 和一个正整数 N，使得对于所有的 n>N，都有 f(g(n)) ≤ c*n 成立。

根据 f(n) = O(n) 的定义，存在正常数 c1 和正整数 N1，使得对于所有的 n>N1，都有 f(n) ≤ c1*n 成立。

同样地，根据 g(n) = O(n) 的定义，存在正常数 c2 和正整数 N2，使得对于所有的 n>N2，都有 g(n) ≤ c2*n 成立。

我们可以选择 c = c1 * c2，并且选择 N = max(N1, N2)。

对于所有的 n>N，我们有：

f(g(n)) ≤ c1 * g(n) （根据 f(n) = O(n)） ≤ c1 * (c2 * n) （根据 g(n) = O(n)） = (c1 * c2) * n = c * n

因此，我们证明了 f(g(n)) = O(n)。