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

Question

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}$$

@Ant100: I think Tom's comment is about the lack of parentheses — robjohn, Jun 23 '14 at 19:46
I think this must be a logarithm base smaller than $2$, otherwise the listed solution of $n=63$ is false... — abiessu, Jun 23 '14 at 19:48
@Ant100: but when you write inline and don't use LaTeX, it is ambiguous whether you are asking about $\log(n/n)$ or $\log(n)/n$. Using LaTeX, you would not need to use parentheses: $\dfrac{\log n}{n}$. — robjohn, Jun 23 '14 at 19:49
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? — Thomas Russell, Jun 23 '14 at 19:50

score 1 · Accepted Answer · answered Jun 23 '14 at 20:00

1

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

answered Jun 23 '14 at 20:00

Thomas Russell

10,425
5
38
66

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] – Thomas Russell 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

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

1 Answers1