1
$\begingroup$

My apologies if the title of the post is a bit confusing...wasn't sure how to word the problem.

I ran across some questions in the form of:

Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size $n$, insertion sort runs in $8n^2$ steps, while merge sort runs in $64n lg n$ steps. For which values of n does insertion sort beat merge sort?

and

What is the smallest value of n such that an algorithm whose running time is $100n^2$ runs faster than an algorithm whose running time is $2n$ on the same machine?

Obviously I can just keep testing the numbers and get the right answer, but I'm wondering what is the correct approach/formula for being able to determine this? I'm not great at math so a really simplified explanation would be much appreciated.

$\endgroup$
1
  • $\begingroup$ These are worst case scenarios right? You could draw a graph and look at where the functions intersect or solve for n algebraically. For your second example, for instance, $100n^{2}$ is always larger than $2n$ for $n\geq1$.. $\endgroup$
    – Epictetus
    Nov 28, 2012 at 16:29

1 Answer 1

2
$\begingroup$

Unfortunately, there's no magic algorithm to solve all possible inequalities you'll encounter. In your first example, you're required to find all $n$ for which $$ 8n^2<64n\lg n $$ You can simplify a bit by dividing both sides of the above inequality by $8n$, which you can do since inequalities are preserved by multiplication or division by positive amounts. That leaves you with the problem of solving $$ n<8\lg n $$ and here you're stuck, since there's no simple way to solve such inequalities. There are some non-algebraic techniques for solving these, but unless you're versed in these or can call upon programs like Mathematica or Maple or are willing to take the time to learn how to ask online solvers like Wolfram Alpha, the best you can do is to try some sample values. In this example, you might try powers of 2 first, since that would make the log easy to calculate, like this: $$ \begin{array}{ccc} \mathbf{n} & \mathbf{8\lg n} & \mathbf{n<8\lg n} \\ 2 & 8 & \text{yes} \\ 4 & 16 & \text{yes} \\ 8 & 24 & \text{yes} \\ 16 & 32 & \text{yes} \\ 32 & 40 & \text{yes} \\ 64 & 48 & \text{no} \end{array} $$ so you know at least that the first $n$ for which $n$ is larger than $8\lg n$ lies somewhere in the range between 32 and 64. To narrow the search you can use bisection, like this: trying the average of 32 and 64, i.e., 48 we find that $48 > 44.68\approx 8\lg48$ so now we know that our solution lies between 32 and 48. The average of 32 and 48 is 40 and $40<42.58\approx 8\lg 40$ so you now know that the solution lies between 40 and 48. Continuing in this vein we eventually find that the last $n$ for which $n<8\lg n$ is $n=43$.

This took some time, but it wasn't all that bad. Fortunately, this is about as nasty as it gets for most applications, since if you're in the context of running times for programs you won't usually see any functions that aren't either polynomials or involve things much more complicated than logs.

$\endgroup$
2
  • $\begingroup$ Just a note; the inequality $n < 8 \log_2 n$ is satisfied when $$1.1 \approx -\frac{8}{\ln 2} W_0\!\left(-\frac{\ln 2}{8}\right) < n < -\frac{8}{\ln 2}W_{-1}\!\left(-\frac{\ln 2}{8}\right) \approx 43.5593,$$ where $W_0$ and $W_{-1}$ are branches of the Lambert W function. $\endgroup$ Nov 28, 2012 at 17:58
  • $\begingroup$ @Antonio. Quite right, but I judged that wouldn't be of much use to a poster who confessed to be "not great at math". $\endgroup$ Nov 28, 2012 at 20:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .