Results 1 to 4 of 4

Math Help - Algorithmic runtime

  1. #1
    Member
    Joined
    Sep 2008
    Posts
    76

    Algorithmic runtime

    we have Algorithm A whose runtime is f(n) = 8*(n^4)+2*(n^3)

    and Algorithm B whose runtime g(n) = 0.25*(n^4) + 3*(n^3) + 5*(n^2)

    Assume we want to write a library function that is given an input of size n,and then selects which of the 2 algorithms to use based on which gives the best runtime for that size.Formally determine the cuttoff for n when the library should stop using one algorithm and should start using the other.Show your work and justify your answer.


    Please help
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by NidhiS View Post
    we have Algorithm A whose runtime is f(n) = 8*(n^4)+2*(n^3)

    and Algorithm B whose runtime g(n) = 0.25*(n^4) + 3*(n^3) + 5*(n^2)

    Assume we want to write a library function that is given an input of size n,and then selects which of the 2 algorithms to use based on which gives the best runtime for that size.Formally determine the cuttoff for n when the library should stop using one algorithm and should start using the other.Show your work and justify your answer.


    Please help

    Find the positive root of f(x)=g(x) , then for any n above the root use B, and below the root use A.

    CB
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2008
    Posts
    76
    CB thanks for your reply.I have a question.SO If i find the positive root of f(n)=g(n) which is 0.90228 and from my limit calculations of the growth rate of the 2 functions and using solving them using the quantified definitions,I figured that f(n) is in the theta of g(n). That means both function grow at the same rate.How can then you say that for any value of n over 0.90228 we could use B and below it we could use A?
    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 NidhiS View Post
    CB thanks for your reply.I have a question.SO If i find the positive root of f(n)=g(n) which is 0.90228 and from my limit calculations of the growth rate of the 2 functions and using solving them using the quantified definitions,I figured that f(n) is in the theta of g(n). That means both function grow at the same rate.How can then you say that for any value of n over 0.90228 we could use B and below it we could use A?
    They grow asymtotically "at the same rate", or rather one is bounded above by a multiple of the other and below by a different multiple of it. Thus asymtotically we could have f(x)/g(x) \sim K where K is a constant. If K is anything other than 1 then one of these is eventually always smaller than the other and so is the run time of a more efficient algorithm.

    In this case A is 32 times slower than B asymtotically.

    CB
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: October 6th 2009, 11:29 AM
  2. Help with empty boxes..algorithmic problem.
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: December 12th 2007, 08:32 AM

Search Tags


/mathhelpforum @mathhelpforum