Results 1 to 5 of 5

Math Help - Point where growth rate of one function overtakes growth rate of another

  1. #1
    Newbie
    Joined
    Aug 2012
    From
    United States
    Posts
    3

    Point where growth rate of one function overtakes growth rate of another

    This is the problem:
    Two algorithms takes n2 days and 2n seconds respectively, to solve an instance of size n.
    What is the size of the smallest instance on which the former algorithm outperforms the
    latter algorithm?

    I was able to get the answer by solving both functions f(n)=86400*n2 and g(n)=2n (86400 since there are that many seconds in a day) for values of n starting with 1 and incrementing. At 26, algorithm 1 becomes more efficient than algorithm 2. I can also get at the same answer by graphing both functions. But I'm sure there has to be another way. I've tried Googling and found information on comparing the growth rates of two functions using limits, but none of those techniques allow me to calculate the minimum n where the slower-growing algorithm becomes more efficient than the faster-growing one. Thanks for any help anyone can give me!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jun 2012
    From
    AZ
    Posts
    616
    Thanks
    97

    Re: Point where growth rate of one function overtakes growth rate of another

    That's basically the solution, find the minimum n such that 86400n^2 \ge 2^n \Rightarrow 86400n^2 - 2^n \ge 0. There's not really any other solution besides, graphing both functions or some guess/check.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2012
    From
    United States
    Posts
    3

    Re: Point where growth rate of one function overtakes growth rate of another

    Ahh, thanks. I was hoping there was a more sophisticated solution like plugging both functions into a formula to get the answer, but if that's the only way then it's the only way.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Point where growth rate of one function overtakes growth rate of another

    The exact real solution to the equation 86400n^2=2^n is not expressible using usual functions. However, it is possible to shorten the search interval by making some estimates. We have 86400n^2 = 2^n is equivalent to log(86400) + 2log(n) = n where logarithm is to the base 2. Next, log(86400) ≈ 16.4, so n > 16. Further, log(16) = 4, so n ≥ 17 + 2 * 4 = 25. As far as the upper bound, log(32) = 5, and 17 + 2 * 5 = 27 < 32, so n ≤ 32. Therefore, it makes sense to search for the breaking point between 25 and 32. As you found, it turns out that the lower bound is almost sharp.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Aug 2012
    From
    United States
    Posts
    3

    Re: Point where growth rate of one function overtakes growth rate of another

    Emakarov, I'm very intrigued by the method you showed to limit the range of n, but I'm afraid quite a bit of it went over my head. I'm going to chew on it for a while and hopefully I will understand it enough to at least be able to ask you a clarifying question or two. Thank you both for your help!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Growth rate of Prime zeta function
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: January 6th 2012, 08:33 PM
  2. Growth Rate
    Posted in the Algebra Forum
    Replies: 1
    Last Post: May 26th 2010, 01:03 AM
  3. Rate of Growth
    Posted in the Calculus Forum
    Replies: 9
    Last Post: February 22nd 2010, 09:14 PM
  4. function growth rate
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: February 13th 2010, 12:35 PM
  5. Replies: 2
    Last Post: October 15th 2009, 06:06 AM

Search Tags


/mathhelpforum @mathhelpforum