# Deciding between two algorithms with similar runtime in two parameters

Let's say I have a problem which depends on two variables, $m$ and $n$. I also have two algorithms for solving the problem. How do I decide which algorithm to use?

For example, say I have an array of unique numbers $A$, not necessarily sorted, and a second sorted array $B$. I want to create a third array $C$ which contains how many times each number in $A$ appears in $B$.

Algorithm 1 runs in time $O(m \lg n)$ and algorithm 2 in $O(m \lg m + n)$.

It seems to me I would need to divide into three cases:

1. $n=\Theta(m)$
2. $n\gg m$
3. $m \gg n$

How would I generally proceed from here?

• In general, assuming you can, try running the algorithms on "real" data (do you have a real application?). See how they perform. Try to see and think if there are some patterns or properties that hold in the input data. Or also, are both algorithms practical? The Big Oh notation might hide huge constants sometimes. Sometimes it is assumed (DFA minimization, planar graphs, ...), that either variable is always larger than the other. – Juho Jul 7 '13 at 13:33
• @Juho This is a general theoretical question. – Robert S. Barnes Jul 7 '13 at 13:55
• "How do I decide which algorithm to use?" -- Is runtime your only concern? – Raphael Jul 7 '13 at 17:50
• @Raphael Yes, it is. – Robert S. Barnes Jul 8 '13 at 13:16

A better comparison is $n$ versus $m\log m$. When $n = \Theta(m\log m)$, both algorithms have running times $\Theta(m\log m)$. When $n \gg m\log m$ (or rather $n = \omega(m\log m)$, the second algorithm has running time $\Theta(n)$ and the first one has running time $\Theta(m\log n) = o(n)$ since $m = o(n/\log n)$. When $n \ll m\log m$ (or rather $n = o(m\log m)$) the second algorithm has running time $\Theta(m\log m)$ and the first one has running time $\Theta(m\log n) = o(m\log m)$.
• There may be heuristics, for example if you have a term $\Theta(f+g)$ then it might be helpful to compare $f$ and $g$. But in the end, the most important skills are general problem solving skills. – Yuval Filmus Jul 9 '13 at 21:26