Question

. 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? Approximately how long does such an instance take to solve?

Answer 1

• n = 1
• 1 day

Explanation:

n^2 is less than 2^n for n < 2 and for n > 4. The smallest size of n that is of interest is n=1. For that, n^2 = 1^1 = 1.

The n^2 algorithm will outperform the 2^n algorithm for n = 1. That problem size will take 1 day to solve.

_____

Please note that there are no algebraic methods for solving an inequality of the form x^2 < 2^x. We have solved it using a graphing calculator.