# Is there a property for log(n)/n?

I found a small exercise which I couldn't figure what to do, so I found a solution. Then I tried to understand it and everything went well until I got to this part:

$$\frac{1}{8} = \frac{\log(n)}{n}$$

Then it just skipped and say that the answer was $n = 43$. I was wondering if there is some kind of property for $\log (n) / n$ I don't know about. Or otherwise, how was this solved?

EDIT: This is the exercise Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in 8n2 steps, while merge sort runs in 64n lg n steps. For which values of n does insertion sort beat merge sort?

And this was the solution given: $$8n^2 = 64n \log(n)$$ $$n^2 = 8n \log(n)$$ $$n = 8 \log(n)$$ $$\frac{1}{8} = \frac{log(n)}{n}$$

-
If $n=1$ you get $0$... is there something missing? – Forever Mozart Jun 23 '14 at 19:42
I don't follow :/ – Ant100 Jun 23 '14 at 19:44
@Ant100: I think Tom's comment is about the lack of parentheses – robjohn Jun 23 '14 at 19:46
Oh, sorry about that, in the book there are no parentheses. – Ant100 Jun 23 '14 at 19:47
In order for your solution of $n=63$ to be correct, the base of the logarithm must be: $$b=3^{16/63} \times 7^{8/63}$$ A rather unusual base!! Are you sure that you're not given more information? – Shaktal Jun 23 '14 at 19:50

If we take your amended question, which asks us to solve the inequality:

$$8n^{2}<64 n \log_{2}(n)$$

We can therefore divide both sides by $64n$ to get:

$$\frac{n}{8}<\log_{2}(n)$$

This has to be solved by numerical methods and we see that we have (by Mathematica):

$$1.1<n\lesssim43.5593$$

And we note that $n$ must be an integer so we have:

$$\lceil 1.1 \rceil=2 <n < 43 = \lfloor 43.5593\rfloor$$

-
Indeed; the given answer of 63 could be a typo for 43, influenced by the presence of 64 in the equation. – Théophile Jun 23 '14 at 20:01
@Théophile I'm terrible sorry I believe you are right, this was a horrible typo. – Ant100 Jun 23 '14 at 20:04
@Shaktal: I'm not sure how you get to n < 43, is it like a convention? – Ant100 Jun 23 '14 at 20:05
@Ant100 One way of arriving at it is the Newton-Raphson iterative method, which is described here. This equation doesn't have a elementary closed form as it is a transcendental equation, but its solutions can be expressed as exponentials of product logs. I got to it by simply using the following Mathematica code: Reduce[n/8 < Log[2,n],n] – Shaktal Jun 23 '14 at 20:06
An exact solution can be expressed in terms of the Lambert W-function. – JacksonFitzsimmons Jun 23 '15 at 18:21