Suppose I have 2 possible algorithms: one runs in O(m+n) and the other runs in O(mn). Suppose also that the task is performed on a connected graph with m edges and n vertices. No other information is given about the graph. How do I know which algorithm is faster?

EDIT: I don't think my question is a duplicate of the question quicksort refers to since that question asks for a definition and I'm asking for a calculation. I did search for a solution before I posted but couldn't find any sufficient solution to my question.


Since big O is only an upper bound, you cannot really tell which algorithm is faster. Let us therefore assume that the running times of the two algorithms are actually $\Theta(n+m)$ and $\Theta(nm)$. Since your graphs are all connected, you have $n-1 \leq m \leq \binom{n}{2}$, and so the first algorithm runs in time $\Theta(m)$ and the second in time $\Omega(m^{1.5})$. This shows that as $m\to\infty$ (equivalently, as $n\to\infty$), the first algorithm is asymptotically faster.


The function O() represent the number of steps to complete a task for a specific algorithm. O(m+n) will be always faster than O(m*n).

[edit] sorry O() is not a function is a notation for classifying algorithm give an estimation (upper bound) of the number of steps for complete a task. If I have to choose between two algorithms for a specific task, one classifies O(m+n) and second classify O(mn), without any other information, I'll choose that classify O(m+n) because it's done with fewer steps.

  • 1
    $\begingroup$ $\mathcal{O}$ is not a function and yours isn't really an answer to OP's question. If you wish to answer, could you be a little more precise? $\endgroup$ – quicksort Mar 7 '17 at 12:02
  • $\begingroup$ Thanks, but I was asking for a way to calculate which algorithm is faster so I could also know, for example, how to compare O(m+n) and O(m^2 * n). $\endgroup$ – yyy Mar 7 '17 at 12:59

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.