Efficient matrix transpose algorithm

Question

I need to transpose a square matrix that's represented by a char array. Is there a way to perform it in less than o(n^2) complexity? Anyway, what's the most cache-efficient way to do it?

Answer 1

No, you can not make it in less then O(n^2) and the reason behind this is that you need to at least touch each element in the matrix once (which is already (n*n). Therefore you can not do better.

The best you can do is to use O(1) additional memory (not time) doing in-place matrix transpose (which is nicely outlined in wikipedia).

Note that you do not always need to calculate transpose matrix. For a lot of applications you can just swap coordinates (if you need A[i][j] - just return A[j][i] -th element)