c - 运行时分析（C）Big-oh notation

Question

考虑一个函数，它的主体是：

sum = 0;

for (i = 1; i <= f(n); i++)
    sum += i;

其中 f(n) 是一个函数调用。给这个函数的运行时间一个简单而严格的 big-oh 上限，作为 n 的函数，假设：

a) The running time of f(n) is O(n), and the value of f(n) is n!
b) The running time of f(n) is O(n), and the value of f(n) is n
c) The running time of f(n) is O(n²), and the value of f(n) is n
d) The running time of f(n) is O(1), and the value of f(n) is 0

我只是想确保我走在正确的轨道上。我的回答：

a) O(n²) 
b) O(n²)
c) O(n³)
d) O(1)

Answer 1

第一个不正确：f(n) 的值为 n!，这是一个阶乘。它生长得非常快。答案应该是 O(n×n!)，因为你正在调用一个运行时间为 O(n) 总共 n 的函数！次。我不确定这是否可以简化。

其他看起来都不错。