Power - Complexity Analysis (Why it's logarithmic)

Each recursive call reduces $n$ by half (when even) or by $1$ (when odd). In the worst case, you halve $n$ about $\log_2(n)$ times before reaching $0$.

Time complexity: $O(\log n)$. You make at most $\log_2(n)$ recursive calls, and each call does $O(1)$ work (one multiplication).

Space complexity: $O(\log n)$ for the recursion stack. You can convert this to an iterative solution to reduce space to $O(1)$, but the time stays $O(\log n)$.