# How can I analyze the time complexity of this Dynamic Time Warping algorithm implemented in MATLAB?

I have a rough idea that the time complexity is O(mn) where m and n are based on the length of signals, as per this http://en.wikipedia.org/wiki/Dynamic_time_warping.

How can I determine the time complexity of the following code (source)

function [Dist,D,k,w,rw,tw]=dtw3(t,r)
%
% [Dist,D,k,w,rw,tw]=dtw(r,t,pflag)
%
% Dynamic Time Warping Algorithm
% Dist is unnormalized distance between t and r
% D is the accumulated distance matrix
% k is the normalizing factor
% w is the optimal path
% t is the vector you are testing against
% r is the vector you are testing
% rw is the warped r vector
% tw is the warped t vector

[row,M]=size(r);
if (row > M)
M=row;
r=r';
end;
[row,N]=size(t);
if (row > N)
N=row;
t=t';
end;

d=((repmat(r',1,N)-repmat(t,M,1)).^2);

D=zeros(size(d));
D(1,1)=d(1,1);

for m=2:M
D(m,1)=d(m,1)+D(m-1,1);
end
for n=2:N
D(1,n)=d(1,n)+D(1,n-1);
end
for m=2:M
for n=2:N
D(m,n)=d(m,n)+min(D(m-1,n),min(D(m-1,n-1),D(m,n-1)));
end
end

Dist=D(M,N);
n=N;
m=M;
k=1;
w=[M N];
while ((n+m)~=2)
if (n-1)==0
m=m-1;
elseif (m-1)==0
n=n-1;
else
[values,number]=min([D(m-1,n),D(m,n-1),D(m-1,n-1)]);
switch number
case 1
m=m-1;
case 2
n=n-1;
case 3
m=m-1;
n=n-1;
end
end
k=k+1;
w=[m n; w];
end

% warped waves
rw=r(w(:,1));
tw=t(w(:,2));
end

• Questions about code are off-topic here. You might try the Stack Overflow or Digital Signal Processing site. If you want to move your question there, click the "flag" button to flag it for moderator attention and ask the moderators to migrate it to the appropriate site. – D.W. Dec 8 '13 at 7:16
• I'm not sure this is off-topic. Questions about writing programs certainly are but is complexity analysis of given code off-topic, too? – David Richerby Dec 8 '13 at 9:54

• There's also the pair of library calls to repmat. I don't know what that does but that could, in theory, dominate the complexity. – David Richerby Dec 8 '13 at 9:57