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

n = 9

Step-by-step 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