Time complexity of recursive power code
An Answer

I will take your code at face value under the Uniform Cost Model.

Let's now assume $n$ is of the form $n = 2^k$ where $k \in \mathbb{N} \wedge k \geq 0$ (e.g. $n$ is a power of $2$).

We then get a recurrence relation like so:

$$\begin{align}
T(x, n) &amp; = 2 \cdot T\left(x,  \frac{n}{2} \right) + c \\[0.5em]
&amp; = 4 \cdot  T\left(x,  \frac{n}{4} \right) + 2c + c \\
&amp; = \vdots \\[0.5em]
&amp; = \sum_{i = 1}^{\log_2 n} 2^{i - 1} \cdot c\\[0.5em]
&amp; = c(n - 1)\\
&amp; = \Theta(n)
  \end{align}$$



Some Fun

Now let's take a step back and check out the Logarithmic Cost Model. Let's define the cost of multiplication as $g(n)$ where $n = \log_2 x$ (the size of $x$ in binary) and $x$ maximum of the two arguments. 

Along with our prior assumption about $n$, let's also assume $x$ is of the form $x = 2^k$ where $k \in \mathbb{N} \wedge k \geq 0$ (e.g. $x$ is a power of $2$).

We get a recurrence of the form:

$$\begin{align}
T(n) &amp; = 2 \cdot T\left(\frac{n}{2} \right) + g\left(\frac{n}{2}\right) \\[0.5em]
&amp; = 4 \cdot  T\left(\frac{n}{4} \right) + 2 \cdot g\left(\frac{n}{4}\right) + g\left(\frac{n}{2}\right) \\
&amp; = \vdots \\[0.5em]
&amp; = \sum_{i = 1}^{\log_2 n} 2^{i - 1} \cdot g\left(\frac{n}{2^i}\right)\\[0.5em]
\end{align}$$

Now we can analyze some interesting multiplication methods:


Multiplication is linear in size, e.g. $g(n) = n$.


$$
\begin{align}
T(n) &amp; = \Theta(n \log n)
\end{align}$$


Multiplication is quadratic in size, e.g. $g(n) = n^2$.


$$\begin{align}
T(n) &amp; = \Theta(n^2)
\end{align}$$


Karatsuba Multiplication, the divide and conquer method, e.g. $g(n) = \Theta(n^{\log_2 3})$


$$\begin{align}
T(n) &amp; = \Theta(n^{\log_2 3})
\end{align}$$


Just for fun, and to plug Yuval's answer to my own question, multiplication is super-linear-polylogarithmic and sub-polynomial-polylogarithmic, e.g. $g(n) = \Theta(n\log n \cdot 2^{\sqrt{2\log n}})$. We also assume size $n$ for $g$ instead of $\frac{n}{2}$.

$$\begin{align}
T(n) &amp; = 2 \cdot T\left(\frac{n}{2} \right) + \Theta\left(n\log n \cdot 2^{\sqrt{2\log n}}\right) \\[0.5em]
\end{align}$$

We use case 3 of the Master Theorem to get:

$$\begin{align}
T(n) &amp; = \Theta\left(n\log n \cdot 2^{\sqrt{2\log n}}\right) \\[0.5em]
\end{align}$$


Essentially, but not exactly, as the time complexity becomes superlinear, the time it takes to multiply overtakes the recursive time. This can be seen as case 3 of the Master Theorem.



Even More Fun!

Now let's say this was implemented in a smart manner, not repeating the recursive calls or using DP.

We get a recurrence of the form:

$$\begin{align}
T(n) &amp; = T\left(\frac{n}{2} \right) + g\left(\frac{n}{2}\right) \\[0.5em]
&amp; = T\left(\frac{n}{4} \right) + g\left(\frac{n}{4}\right) + g\left(\frac{n}{2}\right) \\
&amp; = \vdots \\[0.5em]
&amp; = \sum_{i = 1}^{\log_2 n} g\left(\frac{n}{2^i}\right)\\[0.5em]
\end{align}$$

The major improvement now is when multiplication is linear in size, we now get linear exponentiation!

$$
\begin{align}
T(n) &amp; = \Theta(n)
\end{align}$$