Question

Suppose the running time of Algorithm A is 1000n^2 , and the running time of Algorithm B is n^5 . What is the largest integral value of n for which the running time of Algorithm B is smaller than that of A?

Answer 1

Answer:

n = 9

Explanation:

To find the answer we need to check at what point the running time of algorithm A is equal the running time of B:

1000*n*n = n*n*n*n*n  

1000 = n*n*n = n^3

n = ∛(1000) = 10  (when n equals ten A equal B)

For any integer greater than ten B > A  and for any integer smaller than ten B < A. The greatest integer for which B < A is nine, therefore nine is our answer.  

                    A                                      B

                    1000n^2                          n^5

n = 8             64000              <             32768

n = 9             81000              <             59049

n = 10            100000            =             100000

n = 11             121000             >             161051

n = 12            144000             >             248832