Асимптотическая временная сложность 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 log<sub>a</sub>n terms)
    => T(n) = c*n*(1 - a^log<sub>a</sub>n)/(1 - a)
    => T(n) = c*n*(1 - n)/(1 - a) ~ c*n*(1-n)

Answer 1

Ошибка, предложенная @meowgoesthedog в комментариях, связана с неправильным скачком в рассуждениях (есть лог _{(1 / a)} n терминов, а не лог _a n);правильный вывод выглядит следующим образом:

    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<sub>(1/a)</sub>n terms)
    => T(n) = c*n*(1 - a^log<sub>(1/a)</sub>n)/(1 - a)
    => T(n) = c*n*(1 - n)/(1 - a) ~ c*n*(1-1/n) ~ O(n)