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

This is the problem:

Two algorithms takes n^{2} days and 2^{n} 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*n^{2} and g(n)=2^{n} (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!

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.

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.

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.

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!