Efficient FFT computation of a zero-padded vector
You can decompose the FFT that you describe into some smaller transforms. Take a look at what you're calculating when you zero-pad a vector $x[n]$ of length $N \over 2$ to length $N$ and calculate a DFT:

$$
X[k] = \sum_{n=0}^{\frac{N}{2}-1} x[n] e^{-j2\pi nk \over N}
$$

To split this up into two transforms, first look at just the even-indexed terms in the $N$-point sequence $X[k]$:

$$
\begin{align}
X[2k] &amp;= \sum_{n=0}^{\frac{N}{2}-1} x[n] e^{-j2\pi n2k \over N} \\
&amp;= \sum_{n=0}^{\frac{N}{2}-1} x[n] e^{-j2\pi nk \over \frac{N}{2}}
\end{align}
$$

Via inspection of the above, we can conclude that the even-indexed terms of the zero-padded DFT are just equal to the $\frac{N}{2}$-point DFT of the original input sequence (with no zero-padding). What about the odd-indexed terms?

$$
\begin{align}
X[2k+1] &amp;= \sum_{n=0}^{\frac{N}{2}-1} x[n] e^{-j2\pi n(2k+1) \over N} \\
&amp;= \sum_{n=0}^{\frac{N}{2}-1} x[n] e^{-j2\pi n \over N} e^{-j2\pi nk \over \frac{N}{2}}
\end{align}
$$

This is a similar expression to the even-indexed terms $X[2k]$. We take the original $N\over 2$-length sequence, multiply it by a complex exponential sequence $e^{-j2\pi n \over N}$, then calculate the $N \over 2$-length DFT of the result. This makes intuitive sense if we write the exponential as $e^{-j2\pi 0.5n \over \frac{N}{2}}$: multiplying by such a complex exponential yields a shift in the frequency domain of half of a $N \over 2$-length DFT bin width. This gives the interpolation-by-2 effect that the zero-padding is known to yield.

In summary: To decompose an $N$-point DFT that consists of an $N \over 2$-point signal $x[n]$ followed by $N \over 2$ zeros, do the following:


Calculate an $N \over 2$-point DFT of the original signal $x[n]$. This make up the even-indexed values in the zero-padded DFT result.
Multiply the original signal by the complex exponential function $e^{-j2\pi n \over N}$. Calculate an $N \over 2$-point DFT of the product. This makes up the odd-indexed values in the zero-padded DFT result.


The caveat: While it depends on your DFT size $N$, this may not effect any tangible reduction in complexity beyond just calculating the zero-padded DFT directly. I have an application where I've tried to make a similar optimization myself in the past, although it is on a very different platform from what you described (mine runs on high-performance server machines using highly-optimized FFT libraries like Intel Math Kernel Library). While you may be able to achieve a theoretical reduction in the total number of arithmetic operations that you need, due to other effects like memory accesses, caching, and so on, it's common that trying to do 2 $N \over 2$-point FFTs is slower than just doing one $N$-point FFT directly. In my case, I've never been able to beat the existing library's $N$-point transform.

To estimate the complexity reduction by doing this, we can estimate the number of arithmetic operations that each method needs. Using the rule of thumb that an $N$-point FFT requires approximately $5 N \log N$ arithmetic operations, we can estimate the savings in operations:

$$
\text{savings} = 5 N \log N - \left(2\left(5 \frac{N}{2} \log \frac{N}{2} \right)+5 \frac{N}{2}\right)
$$

$$
\text{savings} = 5 N \log N - \left(5 N \log \frac{N}{2} +5 \frac{N}{2}\right)
$$

The first term in the parentheses counts the approximate number of operations required by the 2 $\frac{N}{2}$-point DFTs, while the second term counts the number of operations needed for the $\frac{N}{2}$-point complex vector multiplication (there are 5 scalar operations per complex multiply).

The problem is, as $N$ increases, the amount of savings diminishes because of the logarithmic scaling of the DFT. For typical DFT sizes, you will likely find that this approach yields little complexity reduction.