# Thread: Inequalities and log base 2 search algorithm problem

1. ## 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.

2. Hello, cgecko!

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

We have two functions: . $y \:=\:x$ .and . $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.

3. 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

4. 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