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?
Complexity of transposing matrices represented as list of row or column vectors
algorithms;lower bounds;matrices
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.