Thread: Inequalities and log base 2 search algorithm problem

I have a problem in my algorithms class that I am unable to solve without using brute force. I'd love to relearn how to solve this (I took my math over a decade ago!)

There's a insertion sort algorithm that runs in 8n2 (8 n-squared) and a merge sort algorithm that runs in 64nlgn (64 n log-base2 of n). For which n does insertion sort run faster than merge sort?

I've started with the equation 8n2 < 64nlgn and simplified this to n<8lgn. With brute force I've discovered this to be true when n<= 43, but the many steps I've tried to solve this equation for n have failed.

Hello, cgecko!

I've started with the equation: .
and simplified this to: .
With brute force I've discovered this to be true when ,
but the many steps I've tried to solve this equation for have failed.

You are not a failure . . . the inequality cannot be solved directly.


We have two functions: . .and .
. . and we ask: When is the straight line below the log curve?

I recommend using a graphing calculator.

Originally Posted by cgecko

I have a problem in my algorithms class that I am unable to solve without using brute force. I'd love to relearn how to solve this (I took my math over a decade ago!)

There's a insertion sort algorithm that runs in 8n2 (8 n-squared) and a merge sort algorithm that runs in 64nlgn (64 n log-base2 of n). For which n does insertion sort run faster than merge sort?

I've started with the equation 8n2 < 64nlgn and simplified this to n<8lgn. With brute force I've discovered this to be true when n<= 43, but the many steps I've tried to solve this equation for n have failed.

This is a mixed algebraic/transcendental problem, that is to find n such that

n=8 lg(n)

Or as we want to use root finding methods we rewrite this as:

f(n) = 8 lg(n) - n = 0.

The only ways of solving this are essentially brute force (that you can do
it by some means is to your credit).

There are a number of ways of systematising brute force searches, my own
favourite is the bisection method, but others might prefer Newton-Raphson
but that requires that f(n) be differentiable.

RonL

Originally Posted by CaptainBlack

This is a mixed algebraic/transcendental problem, that is to find n such that

n=8 lg(n)

This may well have a closed form solution in terms of Lambert's W function,
but I don't have the patience to do it that way just now.

(But the dirty secret about Lambert's W is that it is evaluated using
Newton-Raphson).

RonL