# Comparing complexities with 2 variables

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.
• $\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? – quicksort Mar 7 '17 at 12:02