Results 1 to 4 of 4

Math Help - Inequalities and log base 2 search algorithm problem

  1. #1
    cgecko
    Guest

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,908
    Thanks
    766
    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.

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by cgecko View Post
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by CaptainBlack View Post
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. The Expanding Square Search Pattern Problem
    Posted in the Advanced Applied Math Forum
    Replies: 13
    Last Post: March 30th 2011, 06:09 PM
  2. Replies: 1
    Last Post: March 7th 2010, 07:14 PM
  3. Replies: 3
    Last Post: February 21st 2010, 12:58 AM
  4. Search Algorithm, Numerical Methods
    Posted in the Advanced Applied Math Forum
    Replies: 2
    Last Post: September 6th 2009, 08:41 AM
  5. Binary Search Algorithm
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 11th 2006, 11:57 PM

Search Tags


/mathhelpforum @mathhelpforum