Search code examples
time-complexityrecurrence

Asymptotic time complexity of c*n*(1 - n)

Suppose on solving a recurrence, I find that:

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

where c is a positive constant and n the size of the input

Should I consider the asymptotic time complexity of this recurrence, O(n) as the n^2 term is negative?

UPDATE:

For example, suppose we have the following recurrence:


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

  • The error as suggested by @meowgoesthedog in the comments is due to an incorrect leap in reasoning (there are log(1/a)n terms and not logan); the correct derivation is as follows:

    
    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)