Difference between $O(n^2)$ and $O(m)$ for algorithms on graphs

Given a graph $G$ directed with n nodes and m edges, if an algorithm solves a problem $X$ on $G$ with a complexity $O(n^2)$, while an other algorithm solves same problem $X$ on $G$ but with complexity $O(m)$, what is the most efficient ?

Since $m \in \Theta(n^2)$ in the worst case, $O$-bounds don't tell you much. That is to say, just from these bounds alone, you can't say that $O(m)$ is better than $O(n^2)$ (and the reverse never holds for simple graphs).

However, if you have $\Theta$-bounds then $\Theta(m)$ is properly better than $\Theta(n^2)$ if $m \in o(n^2)$, i.e. you have sparse graphs.

Also, the usual limitations of $O$-worst-case analysis apply: you may actually be interested in typical-case behaviour, constant factors may matter to you, and you need efficiency for finite (small?) $n$.

StackExchange Computer Science Q#44956, answer score: 5