Formula for determining size at which one growth rate beats another? 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.
 A: 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.
