Two M Terms

It finds the shortest linear recurrence a sequence satisfies. Recovering one of order $m$ safely needs at least $2m$ terms, and the algorithm runs in $O(m \log m \log n)$, jumping straight to the $n$-th term by polynomial exponentiation.

It finds the shortest linear recurrence a sequence satisfies. Recovering one of order $m$ safely needs at least $2m$ terms, and the incremental algorithm runs in $O(nm)$, degenerating to $O(n^2)$ when the order is not small.

It finds some linear recurrence a sequence satisfies, not necessarily the shortest. Recovering one of order $m$ safely needs at least $2m$ terms, and the incremental algorithm runs in $O(nm)$, degenerating to $O(n^2)$ when the order is not small.

It finds the shortest linear recurrence a sequence satisfies. Recovering one of order $m$ safely needs at least $m$ terms, and the incremental algorithm runs in $O(nm)$, degenerating to $O(n^2)$ when the order is not small.