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 ?

  • $\begingroup$ Remember to upvote the questions you liked, and accept the one that helped you most. :) $\endgroup$ – Raphael Aug 4 '15 at 10:10

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$.


A bound of the form $O(m)$ is always better than a bound of the form $O(n^2)$ since $m \leq n^2$. As Raphael mentions, since this is only an upper bound, a priori we don't know which algorithm is better. However, if you are interested in sparse graphs (say, $m = O(n)$) then the promise $O(m)$ is better than the promise $O(n^2)$.

Often algorithms are analyzed so that their big O complexity does equal their worst-case complexity. That is, usually an $O(n^2)$ algorithm has time complexity $\Theta(n^2)$ on some inputs, and an $O(m)$ algorithm has time complexity $\Theta(m)$ on some inputs. This doesn't offer any help, since the worst-case instances for the $O(n^2)$ algorithm could be dense.

However, by the same token, graph algorithms are analyzed so that their big O complexity is the best upper bound that can be given in the worst case, where best here roughly means out of all bounds of the form $O(n^\alpha m^\beta)$. This means that usually, if the complexity of an algorithm is quoted as $O(n^2)$, then its complexity is not $O(m)$. However, this is just a convention, and you should check the individual algorithms to make sure.

Don't forget also that asymptotic notation ignores constants – a $\Theta(n^2)$ might be better than a $\Theta(m)$ algorithm for all graphs containing less than $10^{30}$ edges.

  • 1
    $\begingroup$ In my experience, not many authors go to the lengths to show that their $O$-bounds are tight. Hence, I think such conventions are probably misleading -- you know nothing about the true worst-case behaviour of an algorithm if all you have is an $O$-bound you don't know to be tight. (Also, it's beyond me how "let's use $O$ with the convention to mean the bound is tight, if we can" is reasonable; just use $\Theta$ if you know it's tight.) $\endgroup$ – Raphael Aug 2 '15 at 20:56
  • $\begingroup$ It depends on what literature you read. Literature on graph algorithms tries to analyze the algorithm as best as the authors can, though only sometimes the authors also show that the analysis is tight. $\endgroup$ – Yuval Filmus Aug 2 '15 at 21:16
  • 1
    $\begingroup$ I don't see how "$O$-bounds are usually tight" follows from "the authors do their best". $\endgroup$ – Raphael Aug 3 '15 at 5:31
  • $\begingroup$ It doesn't. But in many cases it is clear that the algorithm had roughly that complexity in the worst case, even though the notation doesn't promise that. $\endgroup$ – Yuval Filmus Aug 3 '15 at 5:33

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.