Problem Detail: 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 6×6 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 alot 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 🙂
Asked By : Oxymoron
Answered By : Shaull
The sequence you (correctly) identified sums up to $frac{n(n-1)}{2}=theta(n^2)$, which gives the runtime you were looking for. I’m not sure what you are referring to by “leading constants”. Do you mean you can ignore e.g. $1+2+3$ ? sure, but that will reduce $6$ from the complexity, which is clearly meaningless. On the other hand, you cannot ignore $f(n)$ leading constants for any $f(n)=omega(1)$, so there is really no point in ignoring them altogether.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/10081
