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: 1/8=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?

przesypkai4

przesypkai4

Answered question

2022-07-17

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:
1 8 = 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:
8 n 2 = 64 n log ( n )
n 2 = 8 n log ( n )
n = 8 log ( n )
1 8 = l o g ( n ) n

Answer & Explanation

nezivande0u

nezivande0u

Beginner2022-07-18Added 16 answers

If we take your amended question, which asks us to solve the inequality:
8 n 2 < 64 n log 2 ( n )
We can therefore divide both sides by 64 n to get:
n 8 < log 2 ( n )
This has to be solved by numerical methods and we see that we have (by Mathematica):
1.1 < n 43.5593
And we note that n must be an integer so we have:
1.1 = 2 < n < 43 = 43.5593

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?