[Solved]: Complexity of transposing matrices represented as list of row or column vectors

Problem Detail: 

Given [[1,4,7],[2,5,8],[3,6,9]] which is a list of the column vectors of matrix

|1, 2, 3| |4, 5, 6| |7, 8, 9| 

is $ \Omega(n^2) $ a lower bound for transposing? Assume the matrix is not always square. I have to touch each element at least once, because going from 2 x 5 to 5 x 2 matrix for example, will mean going from a list of 5 lists to a list of 2 lists, so I can't really do any tricks with the array indices, right?

Is there a faster way to transpose matrices?

Asked By : amallya

Answered By : Yuval Filmus

If the matrices are stored in the usual way, that is as long vectors, then the complexity is $\Theta(n^2)$. The reason is that if all the off-diagonal entries in the matrix are different, you will need to change all of them, and there are $n^2-n$ of them.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10636