Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
If $n=1$ you get $0$... is there something missing? –  Forever Mozart Jun 23 at 19:42
    
I don't follow :/ –  Ant100 Jun 23 at 19:44
    
@Ant100: I think Tom's comment is about the lack of parentheses –  robjohn Jun 23 at 19:46
    
Oh, sorry about that, in the book there are no parentheses. –  Ant100 Jun 23 at 19:47
1  
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 at 19:50

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
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 at 20:01
    
@Théophile I'm terrible sorry I believe you are right, this was a horrible typo. –  Ant100 Jun 23 at 20:04
    
@Shaktal: I'm not sure how you get to n < 43, is it like a convention? –  Ant100 Jun 23 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 at 20:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.