I am reading Skiena's Algorithm Design Manual, and he says that if we change $a^n$ to $(a^{n/2})^2$, the exponent is halved at the cost of, at most, 2 multiplications so the algorithm is now $O(\log n)$.
I can't understand how it's $O(\log n)$. We are performing $n/2+1$ multiplications during exponentiation so shouldn't the algorithm be $O(n/2)$?