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

This is the problem:
Two algorithms takes n² days and 2ⁿ 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² and g(n)=2ⁿ (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!

That's basically the solution, find the minimum such that . There's not really any other solution besides, graphing both functions or some guess/check.

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.

The exact real solution to the equation is not expressible using usual functions. However, it is possible to shorten the search interval by making some estimates. We have 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.

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!