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.