# Inequalities and log base 2 search algorithm problem

• Aug 28th 2007, 08:07 AM
cgecko
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.
• Aug 29th 2007, 06:36 AM
Soroban
Hello, cgecko!

Quote:

I've started with the equation: .$\displaystyle 8n^2 \;< \;64n\log_2(n)$
and simplified this to: .$\displaystyle n\;<\;8\log_2(n)$
With brute force I've discovered this to be true when $\displaystyle n \leq 43$,
but the many steps I've tried to solve this equation for $\displaystyle n$ have failed.

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

We have two functions: .$\displaystyle y \:=\:x$ .and .$\displaystyle y \:=\:8\log_2(x)\:=\:\log_2\left(x^8\right)$
. . and we ask: When is the straight line below the log curve?

I recommend using a graphing calculator.

• Aug 29th 2007, 12:52 PM
CaptainBlack
Quote:

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
• Aug 29th 2007, 01:20 PM
CaptainBlack
Quote:

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