View Single Post
Old 2020-12-30, 09:50   #1
carpetpool's Avatar
Nov 2016

22·83 Posts
Post Computation of P-Recursive Sequences in Polynomial Time

Is it possible for centered trinomial coefficients to be computed in O(log n) time, analogous to how the time complexity of modular exponentiation is O(log n)?

I am well aware that factorials cannot be computed in logarithmic time, making Wilson's theorem impractical for large numbers.

On the other hand, raising an integer to a power can easily be done in logarithmic time, making Fermat's test practical for large numbers.

Where does computing centered trinomial coefficient (and similar sequences), fall into?

To be clear, central trinomial coefficients are the coefficient of x^n in (x^2 + x + 1)^n for n ≥ 0.

Meanwhile, centered binomial coefficients binomial(2*n, n) are the coefficient of x^n in (x^2 + 2x + 1)^n for n ≥ 0.

Catalan numbers have the form binomial(2*n, n)/(n + 1) for n ≥ 0. I can't name a single algorithm for computing either central binomial coefficients or Catalan numbers in O(log n) time.

Is the same true for centered trinomial coefficients, and if so, why is it impossible to compute any particular term in O(log n) time?
carpetpool is offline   Reply With Quote