patternMinor
What is the complexity of this matrix transposition?
Viewed 0 times
thisthewhattranspositionmatrixcomplexity
Problem
I'm working on some exercises regarding graph theory and complexity.
Now I'm asked to give an algorithm that computes a transposed graph of $G$, $G^T$ given the adjacency matrix of $G$. So basically I just have to give an algorithm to transpose an $N \times N$ matrix.
My first thought was to loop through all rows and columns and simply swapping values in each of the $M[i,j]$ place, giving a complexity of $O(n^2)$. But I immediately realized there's no need to swap more than once, so I can skip a column every time e.g. when I've iterated over row $i$, there's no need to start iteration of the next row at column $i$, but rather at column $i + 1$.
This is all well and good, but how do I determine the complexity of this? When I think about a concrete example, for instance a 6x6 matrix, this leads to 6 + 5 + 4 + 3 + 2 + 1 swaps (disregarding the fact that position $[i,i]$ is always in the right position if you want to transpose a $N \times N$ matrix, so we could skip that as well).
This looks a lot like the well-known arithmetic series which simplifies to $n^2$, which leads me to think this is also $O(n^2)$. There are actually $n^2/2$ swaps needed, but by convention the leading constants may be ignored, so this still leads to $O(n^2)$. Skipping the $i,i$ swaps leads to $n^2/2 - n$ swaps, which still is $O(n^2)$, but with less work still.
Some clarification would be awesome :)
Now I'm asked to give an algorithm that computes a transposed graph of $G$, $G^T$ given the adjacency matrix of $G$. So basically I just have to give an algorithm to transpose an $N \times N$ matrix.
My first thought was to loop through all rows and columns and simply swapping values in each of the $M[i,j]$ place, giving a complexity of $O(n^2)$. But I immediately realized there's no need to swap more than once, so I can skip a column every time e.g. when I've iterated over row $i$, there's no need to start iteration of the next row at column $i$, but rather at column $i + 1$.
This is all well and good, but how do I determine the complexity of this? When I think about a concrete example, for instance a 6x6 matrix, this leads to 6 + 5 + 4 + 3 + 2 + 1 swaps (disregarding the fact that position $[i,i]$ is always in the right position if you want to transpose a $N \times N$ matrix, so we could skip that as well).
This looks a lot like the well-known arithmetic series which simplifies to $n^2$, which leads me to think this is also $O(n^2)$. There are actually $n^2/2$ swaps needed, but by convention the leading constants may be ignored, so this still leads to $O(n^2)$. Skipping the $i,i$ swaps leads to $n^2/2 - n$ swaps, which still is $O(n^2)$, but with less work still.
Some clarification would be awesome :)
Solution
You can also "transpose" a matrix in $O(1)$ time and space. Maintain a bit $t$ for your matrix $M$. Whenever $M$ is transposed, flip $t$. Now, consider accessing an entry in $M$. If $t$ is set to true, return $M[j,i]$ instead of $M[i,j]$. This trick is arguably cheating, but not always is the matrix actually needed to be transposed. This might work nicely depending the situation.
Context
StackExchange Computer Science Q#10081, answer score: 9
Revisions (0)
No revisions yet.