Compute xn (x raised to the power n). The naive approach multiplies x by itself n times, which takes O(n) time.
But you can do better using logarithms. The key observation: xn=(xn/2)2 when n is even. This lets you halve the exponent at each step.
Before reading the solution, think about this: how many times can you halve n before reaching 1? That's your clue to the time complexity.