c*n*(1 - n) 的渐近时间复杂度

Question

假设解决一个递归问题，我发现：

T(n) = c*n*(1-n) = c*n - c*n^2

其中 c 是正常数，n 是输入的大小

我是否应该考虑这种递归的渐近时间复杂度，O(n)，因为 n^2 项是负数？

更新：

例如，假设我们有以下循环：

    T(n) = T(a*n) + O(n), where the factor a less than 1:
    => T(n) = c*n*(1 + a + a^2 + a^3 + ... for logan terms)
    => T(n) = c*n*(1 - a^logan)/(1 - a)
    => T(n) = c*n*(1 - n)/(1 - a) ~ c*n*(1-n)

Answer 1

@meowgoesthedog 在评论中提出的错误是由于推理中的错误飞跃（有 log_(1/a)n 项而不是 log_an);正确推导如下：

    T(n) = T(a*n) + O(n), where the factor a less than 1:
    => T(n) = c*n*(1 + a + a^2 + a^3 + ... for log(1/a)n terms)
    => T(n) = c*n*(1 - a^log(1/a)n)/(1 - a)
    => T(n) = c*n*(1 - n)/(1 - a) ~ c*n*(1-1/n) ~ O(n)