Algoritmo eficiente: $(y+1)^n$

Question

Dado $y,n\in\mathbb{N}$ y conocer el valor $y^n$ ¿existe una forma eficiente de calcular $(y+1)^n$ ? Cualquier cosa más rápida que el teorema del binomio es bienvenida.

Answer 1

Creo que el conocimiento de $y^n$ no puede acelerar $O(\log n)$ algoritmo de exponenciación al cuadrado . El teorema del binomio le dará $O(n)$ en el mejor de los casos.