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
