Power - Naive Approach

The simplest solution: start with 1, multiply by $x$ exactly $n$ times.

If $n = 5$, you compute $1 \times x \times x \times x \times x \times x$. This takes $O(n)$ time.

For small $n$, this works fine. But if $n = 10^9$, you're doing a billion multiplications. That's too slow. Can you cut the work in half somehow?