Solving when x is in exponent and elsewhere

[algenon]

I found this equation: 8 n^2 = 64 n lgn and would like to solve it.

I rearranged it to get n = 8 lg n

I also think it can be expressed as 2^(n/8) = n/8

The problem came from 'Introduction to Algorithms' by Cormen etc. It states that:

1.2-2
Suppose we are comparing implementations of insertion sort and merge sort on the
same machine. For inputs of size n, insertion sort runs in 8n^2 steps, while merge
sort runs in 64n lg n steps. For which values of n does insertion sort beat merge
sort?

 

[Deleted member 4993]

I found this equation: 8 n^2 = 64 n lgn and would like to solve it.

I rearranged it to get n = 8 lg n

I also think it can be expressed as 2^(n/8) = n/8

The problem came from 'Introduction to Algorithms' by Cormen etc. It states that:

1.2-2
Suppose we are comparing implementations of insertion sort and merge sort on the
same machine. For inputs of size n, insertion sort runs in 8n^2 steps, while merge
sort runs in 64n lg n steps. For which values of n does insertion sort beat merge
sort?

Plot
y = x ..........and............y = 8*ln(x)

Now find the point of intersection. If you know Newton's algorithm of finding roots of polynomials, you could approximate the solution.

You cannot get an exact solution of "that" equation using algebra.

 

[algenon]

That is interesting. Is there an algorithm that can be used to show it is not (exactly) soluble?

 

[Deleted member 4993]

That is interesting. Is there an algorithm that can be used to show it is not (exactly) soluble?

I don't know of any algorithm along that line - just experience. Haven't seen exact solution of that equation.

 

[algenon]

The next problem in the book looks like it might be analagous. It is:

1.2-3
What is the smallest value of n such that an algorithm whose running time is 100n^2
runs faster than an algorithm whose running time is 2^n on the same machine?

Do you think that is insoluble by algebra?

 

[Deleted member 4993]

The next problem in the book looks like it might be analagous. It is:

1.2-3
What is the smallest value of n such that an algorithm whose running time is 100n^2
runs faster than an algorithm whose running time is 2^n on the same machine?

Do you think that is insoluble by algebra?

Yes. If n is an integer, trial& error method can solve it quickly.