Sorry about asking such an elementary question, but I have been wondering about this exact definition for a while. What power of $n$ is $\log(n)$. I know that it is $n^\epsilon$ for a very small ...
Proof of a lower bound $\lambda(n)$ of the smallest number of multiplications $\ell(n)$ needed to compute $a^n$ for an integer $a$
Let $\ell(n)$ be the smallest number of multiplications needed to compute $a^n$ for any integer $a$. Here, a multiplication is $a_i := a_j \cdot a_k$ for $j, k < i$ and $a_0 := a$, e.g. $\ell(8) = ...