1
$\begingroup$

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?

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

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

$\endgroup$
  • $\begingroup$ Is there a general way of deciding these types of problems? Like looking at the asymptotically dominant function in each solution? $\endgroup$ – Robert S. Barnes Jul 9 '13 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$ – Yuval Filmus Jul 9 '13 at 21:26

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.