Power - The Insight (Squaring trick)

To compute $x^8$, you could multiply $x$ eight times. But notice: $x^8 = (x^4)^2 = ((x^2)^2)^2$. You only need three squaring operations instead of seven multiplications.

When $n$ is even, use $x^n = (x^{n/2})^2$. When $n$ is odd, use $x^n = x \cdot x^{n-1}$. Each step reduces the exponent, moving toward the base case $n = 0$ (which returns $1$).

How many steps does this take? You halve $n$ each time (roughly), so you need $O(\log n)$ steps. This is exponentiation by squaring.