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?

  • 3
    $\begingroup$ 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. $\endgroup$
    – Juho
    Jul 7, 2013 at 13:33
  • $\begingroup$ @Juho This is a general theoretical question. $\endgroup$ Jul 7, 2013 at 13:55
  • 1
    $\begingroup$ "How do I decide which algorithm to use?" -- Is runtime your only concern? $\endgroup$
    – Raphael
    Jul 7, 2013 at 17:50
  • $\begingroup$ @Raphael Yes, it is. $\endgroup$ Jul 8, 2013 at 13:16

1 Answer 1


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

  • $\begingroup$ Is there a general way of deciding these types of problems? Like looking at the asymptotically dominant function in each solution? $\endgroup$ Jul 9, 2013 at 6:47
  • $\begingroup$ 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. $\endgroup$ Jul 9, 2013 at 21:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.