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

• Aug 11th 2012, 12:34 PM
vpoko
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!
• Aug 11th 2012, 12:38 PM
richard1234
Re: Point where growth rate of one function overtakes growth rate of another
That's basically the solution, find the minimum \$\displaystyle n\$ such that \$\displaystyle 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.
• Aug 11th 2012, 12:41 PM
vpoko
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.
• Aug 11th 2012, 01:02 PM
emakarov
Re: Point where growth rate of one function overtakes growth rate of another
The exact real solution to the equation \$\displaystyle 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 \$\displaystyle 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.
• Aug 11th 2012, 01:22 PM
vpoko
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!