How can I prove by induction that the second of these two algorithms is faster?

Question

I have two algorithms.

A. Solves problem in 2^n seconds.

B. Solves problem in n^2 + 1,000,000 seconds.

How can I inductively prove that B is faster than A.

I'm told that 2^n > 2n+1 for n>2 might be useful for this problem. I've been cracking my head and can't solve this problem. Thanks.

"n" is equivalent to the size of the program.

EDIT: For all n > 19.

SOLUTION:

Premise: n^2 + 1,000,000 < 2^n

Basis:
n = 20
1000400 < 1048576 TRUE

Induction:

(n+1)^2 + 1000000 > 2^(n+1)
n^2 +2n +1 +1000000 > 2^(n+1)
Apply 2^n > 2n + 1
n^2 + 1000000 > 2^(n+1)

This last line implies that B is always bigger than A.

Answer 1

As you said the base case is proven. ie k^2<2^k for k>=5

For the induction, let us assume that

k^2<2^k

We need to prove that

(k+1)^2<2^(k+1)

(k+1)^2 = k^2 + 2k + 1 < 2^k + 2k + 1

We know that (k-1)^2>=0. thus k^2>=2k-1

2^k + 2k + 1 = 2^k + 2k -1 + 2 <= 2^k + k^2 + 2 < 2^k + 2^k +2= 2^(k+1) + 2

Argh, i feel like im almost there. any help?

Answer 2

B will only be faster if n > 19.9321. If you don't need the actual work, then here is where I got the answer from.

For any numbers less than 19.9321, then A will be faster.

Answer 3

Python as a calculator:

>>> n = 20
>>>
>>> 2**n
1048576
>>> n**2 + 1000000
1000400
>>>