Является ли рост биномиальной функции коэффициента факториальной или полиномиальной?

Question

Я написал алгоритм, который дает список слов, должен проверять каждую уникальную комбинацию из четырех слов в этом списке слов (независимо от порядка).

Количество проверяемых комбинаций, x, можно рассчитать с использованием биномиального коэффициента, т. е. x = n!/(r!(n-r)!) где n общее количество слов в списке и r это число слов в каждой комбинации, которое в моем случае всегда 4, поэтому функция x = n!/(4!(n-4)!) = n!/(24(n-4)!), Следовательно, как общее количество слов, n, увеличивает количество проверяемых комбинаций, x, следовательно, увеличивается факториально верно?

Меня бросило то, что WolframAlpha смогла переписать эту функцию как x = (n^4)/24 − (n^3)/4 + (11.n^2)/24 − n/4так что теперь, казалось бы, расти полиномиально как n растет? Так что это?!

Вот график, чтобы визуализировать рост функции (буква х переключается на л)

Answer 1

Для фиксированного значения r эта функция равна O(n^r). В вашем случае, r = 4, это O(n^4). Это потому, что большинство терминов в числителе отменяются знаменателем:

n!/(4!(n-4)!) 
   = n(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)...(3)(2)(1) 
     -------------------------------------------
     4!(n-4)(n-5)(n-6)...(3)(2)(1)

   = n(n-1)(n-2)(n-3)
     ----------------
           4!

Это полином 4-й степени по n.