The complexity of zero padded DFTs
The classic complexity measures are much less relevant today than they were in the days of fixed point ALU's taking 40 cycles to do a floating point multiply.  

The answer to your question is maybe.  One can decompose an FFT in terms of smaller FFTs,

based on 


  Rabiner, Lawrence R., and Bernard Gold. "Theory and application of
  digital signal processing." Englewood Cliffs, NJ, Prentice-Hall, Inc.,
  1975. 777 p. (1975).


there is a section that shows how to do a 1 dimensional dft in two dimensions.

see my answer at

Combine FFT&#39;s of shorter length than sample data to get spectrum of all data

and coppying the matlab code from there:

for a 96 point FFT, I formed a 32 X 3 matrix


clear all
M=3;
N=32;
x=linspace(0,10,M*N);
X=reshape(x,N,M).'; % read in as rows
Twiddle=zeros(size(X));
for i=1:M
for k=1:N
Twiddle(i,k)=exp(-1j*2*pi*(i-1)(k-1)/(NM));
end
end
X=fft(X) % fft on each column
X=X.*Twiddle;% element by element product
X=fft(X.').' ; %fft on each row
y=reshape(X,N*M,1); % read out as columns
figure(1)
plot(abs(y),'linewidth',2)
title('Composite DFT')
figure(2)
plot(abs(fft(x)),'linewidth',2)
title('Direct DFT')
figure(3)
plot(x,'linewidth',2)
title('time series')



You need to exploit the zero padding when you form the 2D Matrix. When you do the column FFT operation, simplify by noting the zero elements.

As a simple example, let's say we have 3 data points we want to zero pad for a 16 point DFT. A direct DFT is complexity $16^2$. We need to choose M and N, so that M*N=16. I want all the non zero data in the first row, so M=N=4 , so read in as rows is:
$$
X=\left| \begin{array}{cccc} x[0] &amp; x[1] &amp; x[2] &amp; 0 \\
 0 &amp; 0 &amp; 0 &amp; 0 \\
 0 &amp; 0 &amp; 0 &amp; 0 \\
 0 &amp; 0 &amp; 0 &amp; 0 \\
\end{array}\right|
$$
the next step is to do DFTs on the column, normally $ 4 \times 4^2$ complexity. The last column are zeros, and the DFT of a column is zero, so 
our complexity is now $ 3\times 4^2$. Im reusing the same memory, 
$$
\text{after column DFTs} \; \;X=\left| \begin{array}{cccc}
 x[0] &amp; x[1] &amp; x[2] &amp; 0 \\
 x[0] &amp; x[1] &amp; x[2] &amp; 0 \\
 x[0] &amp; x[1] &amp; x[2] &amp; 0 \\
 x[0] &amp; x[1] &amp; x[2] &amp; 0 \\
\end{array}\right|
$$
There was only one term in each column so I didn't really need to do any multiplies in this step and you don't either.
The Twiddle matrix is usually calculated offline in any FFT , and  forming it is not usually counted in the Complexity calculation.
In most DSP treatments, the top of the array is zero based, but in Matlab is one based.
so in MATLAB 
$$ W_{16}^{ik}=
\exp(-\jmath 2\pi\frac{(i-1)(k-1)}{16})
$$
but in most DSP books
$$ W_{16}^{ik}=
\exp(-\jmath 2\pi\frac{(i)(k)}{16})
$$

In this case the product of the Twiddle matrix with $X$ is:
$$ 
\text{Twiddled X} X=\left| \begin{array}{cccc}
x[0] &amp; x[1]1 &amp; x[2]1 &amp; 0 \\
x[0] &amp; x[1]W_{16}^1 &amp; x[2]W_{16}^2 &amp; 0\\
x[0] &amp; x[1]W_{16}^2 &amp; x[2] W_{16}^4 &amp; 0\\
x[0]&amp; x[1]W_{16}^3 &amp; x[2]W_{16}^6 &amp; 0\\
\end{array}\right| \; 
$$
given
$$ 
\text{Twiddle}\; X=\left| \begin{array}{cccc}
1 &amp; 1 &amp; 1 &amp; 1 \\
1 &amp; W_{16}^1 &amp; W_{16}^2 &amp; W_{16}^3 \\
1 &amp; W_{16}^2 &amp; W_{16}^4 &amp; W_{16}^6\\
1 &amp; W_{16}^3 &amp; W_{16}^6 &amp; W_{16}^{9} \\
\end{array}\right| \; 
$$
at this step 9 Complex products

The rest should be obvious (and is left as an exercise) 
Use the Matlab code as a template but do the short cuts when you can.