algorithm - 如果 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)？

标签： algorithmtime-complexitybig-o

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)。