need approach to solve given logarithm expression

Question

I was going through algorithm on sorting and encountered a logarithm problem which need to be solved.

Question Statement is: For inputs of size n, insertion sort runs in $8n^2$ steps, while merge sort runs in $64n\log_2n$ steps. For which values of n does insertion sort beat merge sort?

I tried to break down the problem as: $$8n^2 \leq 64n \log_2n$$ $$ n \leq 8 \log_2n$$ $$ 2^n≤n^8$$

Beyond this I am unable to proceed in equation. So need suggestion on how to proceed further. One way I am thinking of to plot graph for both functions and get intersection point. But I want to solve this using equations.

Answer 1

As matt biesecker commented, the explicit solution is given by Lambert function. As pointed out by matt in a comment, the equation should be $$f(n)=2^n - n^8=0$$ the solution of which being $$n=-\frac{8 }{\log (2)}W_{-1}\left(-\frac{\log (2)}{8}\right)\approx 43.5593$$ In fact, any equation which can be set as $A+Bx+C\log(D+Ex)=0$ has solutions expressed in terms of Lambert function.

If you cannot use it, then numerical methods are the only way and Newton is probably the simplest. In order to make the function smoother, let us rewrite it as $$g(x)=n\log(2)-8\log(n)=0$$ $$g'(x)=\log (2)-\frac{8}{n}$$ So, the function goes through an extremum for $n=\frac 8{\log(2)}\approx 11.5416$ and the second derivative test shows that it is a minimum. Starting from a guess $n_0$, the method will update it according to $$n_{k+1}=n_k-\frac{g(n_k)}{g'(n_k)}$$ It is obvious that the solution is larger than $12$. So, being lazy, let us choose $n_0=12$ and proceed. Newton method generates the following iterates $448.604$, $60.4891$, $44.2504$, $43.5612$, $43.5593$ which is the solution for six significant figures.

There are very good approximation of Lambert function such as $$W_{-1}(a)\approx L_1-L_2+\frac{L_2}{L_1}+\frac{L_2(L_2-2)}{2L_1^2}+\frac{L_2(2L_2^2-9L_2+6)}{6L_1^3}+\cdots$$ where, for the case of $a<0$, $L_1=\log(-a)$, $L_2=\log(-L_1)$. This would give an estimate of $39.4542$ which would be a definitely much better starting value.

So $2^{n} \leq n^8$ holds for any $n$ smaller or equal to this root.

Answer 2

Three ways I can think of (I am not familiar with Lambert-W function which Alpha suggests):

1. Plotting (works)

2. Trial and error (You can skip for $n<8$ for which $2^{n-8}\le1$ and stop for $n<15$, (randomly took n=20, saw that it doesn't work, kept reducing it by stepsof 5)

3. Approximation as explained in this answer in similar question to determine upper limit, (put $n_{old}=15$, it should stop at 12)