4
$\begingroup$

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 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 :)

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ One pedantic note: you need to be a little more specific about what you mean by 'the transposed graph $G^T$' - the obvious assumption is that it's using the same representation as your input is given in (i.e., an adjacency matrix), but that should be explicitly specified both in the original problem and your version of it. Also, canonically the problem should specify whether you're allowed to do it 'in-place' or not - note that your idea for shaving off half the steps only works if you're allowed to return the result in-place. $\endgroup$ – Steven Stadnicki Feb 26 '13 at 3:54
  • $\begingroup$ (In fact, the 'in-place' swapping algorithm actually executes more assignment statements than a naive algorithm that copies everything into its appropriate place in a second given matrix - you should be able to prove this fairly easily with what you know; it's a good lesson on making sure that you know what you're counting when you talk about the complexity!) $\endgroup$ – Steven Stadnicki Feb 26 '13 at 3:56
  • 1
    $\begingroup$ You might be interested in reading this question, and this answer to a similar question. $\endgroup$ – Paresh Feb 26 '13 at 17:24
6
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I mean constants and lower order terms will be ignored in asymptotic complexity. E.g. in somethig that looks like $O(3n^3 + n^{2.81}/2 + 1)$ the lower order terms will be abstracted away, so it becomes $O(n^3)$. This is off course handy when analyzing an algorithm, but it also hides some facts away. Like for example, in my second (and third) algorithm I know for fact it will NEVER actually do NxN swaps... Should I then resort to theta or some other notation? $\endgroup$ – Oxymoron Feb 25 '13 at 14:05
  • $\begingroup$ The exact number of swaps is irrelevant to the complexity analysis. Indeed, it will do $\frac{n(n-1)}{2}$, which is even less than $\frac{n^2}{2}$. If you work with asymptotic analysis, this is still $\theta(n)$. By the way, this is not "resorting to", it is just saying that this is also a lower bound for the algorithm (in the worst case). If you want to emphasize that this algorithm is better than the naive one, then simply don't use asymptotic notation, but explicitly write the number of swaps, as you did. $\endgroup$ – Shaull Feb 25 '13 at 14:34
6
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ Juho: The data in the memory still remains the same column- or row-major 1D array so depending on what programming language looping over i and j and accessing M[i,j] will be fast(slow) and accessing M[j,i] will be slow(fast) due to cache thrashing. When accessing an element from the matrix the neighbouring elements of the 1D array will be loaded into the CPU cache so having the row index change most quickly for row-major ordering will be much faster than if the column index varies most rapidly. So any operation you wish to perform with the transposed matrix is going to be hugely expensive, pre $\endgroup$ – Lindon Jul 25 '13 at 22:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.