What's the transpose complexity Big O in Matlab?

a = [1 2 3 4]

b = a' %what's the Big O complexity here for transposing the "a" 1D array.

a = [ [1 2 3 4] ; [5 6 7 8] ; [9 10 11 12]]

b = a' %what's the Big O complexity here for transposing the "a" 2D array.

Answer 1

[Walter Roberson]

%what's the Big O complexity here for transposing the "a" 1D array.

O(1) -- that is, constant in the size of the array.

%what's the Big O complexity here for transposing the "a" 2D array

In theory, each element only needs to be touched once, so for an n x m matrix it would be O(n*m). (In practice, you need to worry about cache-line conflicts and cache sizes, so the most efficient algorithms in practice involve block algorithms and multiple CPUs, and calculating execution time for them gets more complex.)

[Mohamed Mohsen]

Thanks for your quickly response,

So, your answer is that in case of 1D array it will be a constant with O(1) while in case of 2D array it will be O(n * m) and "m" is O(1) as previously descriped, therefore, the 2D array will become O(N)? is that what are you meaning here?

Thanks in advance.

[Walter Roberson]

No, transposing a 2D array is not a matter of transposing a number of 1D arrays.

MATLAB stores vectors in increasing memory locations, and it keeps a header describing what the size is. For example for the 1 x 4 vector, it would store the information 2 (number of dimensions) and [1 4] (the dimensions), and it would store the data as well. The transpose of a vector involves the same elements in the same order, just with index relabled, (1,K) -> (K,1) . That can be implemented internally in MATLAB by just changing the header from 2, [1 4], to 2, [4 1] (same number of dimensions, but now 4 rows and 1 column.) It is a "reshape" operation, and in MATLAB, all reshape operations that do not move the relative locations in memory of values are implimented by creating a new size header instead of by moving anything in memory.

This strategy does not work for 2D arrays, as the relative locations of values has to change. For 2D or more arrays, to transpose, MATLAB has to make copies of values into new locations. Each value only has to be copied once, so the number of operations (other than for constructing the header) is the same as the number of values in the array.

Internally, the transpose operation on a 2D array for small arrays works like

output = zeros(size(Input,2), size(Input,1), class(Input));
for row = 1 : size(Input,1)
    for col = 1 : size(Input,2)
        output(col,row) = Input(row, col);
    end
end

This is one read operation and one write operation for each input element, but big-O notation drops constant values (e.g., O(2*m*n) is simplified to O(m*n)

[Mohamed Mohsen]

Okay, I got it :))

Thanks a lot.