MATLAB: What is the complexity of the permute() fonction for multiway arrays

MATLABpermutespeed

Some functions to manipulate arrays, such as the "reshape" function, seem to run in O(1). On the other hand, the "permute" function runs quite slowly for larger arrays, especially multiway arrays.
Is it possible to bound the numerical complexity of the "permute" function? I guess my question relates to how "permute" is internally implemented.

Best Answer

The complexity of PERMUTE(A,P) is O(numel(A)) regardless p, but with the constant O depends on p, for example when p=1,2...,d, it will be significantly faster due to linear memory access, but still O(n).
I have no idea how it's implemented internally. There can be so many variants for such problem.
That's why if you can trade permute by reshape, don't hesitate.
Timing and test code
function t = timepermute
p = perms(1:3);
n3 = 10:10:100;
t = zeros(size(p,1),length(n3));
for j = 1:length(n3)
A=rand(1000,1000,n3(j));
for i=1:size(p,1)
pi = p(i,:);
tic
B = permute(A,pi);
t(i,j) = toc;
end
end
s = arrayfun(@(i) sprintf('p = %s',mat2str(p(i,:))), 1:size(p,1),'unif',0);
close all
plot(n3*size(A,1)*size(A,2),t);
xlabel('n');
ylabel('permute time [s]');
legend(s,'location','northwest')
grid on