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?