0
$\begingroup$

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
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W. Dec 8 '13 at 7:16
  • $\begingroup$ I'm not sure this is off-topic. Questions about writing programs certainly are but is complexity analysis of given code off-topic, too? $\endgroup$ – David Richerby Dec 8 '13 at 9:54
1
$\begingroup$

Look at the main double for loop that does all the work. It loops for m from 2 to M and then inside that for n from 2 to N. This is O(MN) like you expected.

$\endgroup$
  • $\begingroup$ And does part of the code following that? I believe that doesn't modify the complexity in anyway right? (I have still new to analyzing code to find this). $\endgroup$ – sj22 Dec 8 '13 at 8:03
  • $\begingroup$ Yeah in the part of the code after that either n or m or both decrease in each iteration. So there can be at most O(N + M) work in that part, which is less than the O(MN) from the first part. $\endgroup$ – Aaron Dec 8 '13 at 8:06
  • $\begingroup$ 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. $\endgroup$ – David Richerby Dec 8 '13 at 9:57
  • $\begingroup$ I don't think so. That's just used to generate a matrix of repeating array patterns. Easier explanation here. It's just another way to initialize. $\endgroup$ – sj22 Dec 8 '13 at 18:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.