3) An algorithm has a run time of O (nk) for some integer k. On an input of size 500, the algorithm takes 16 seconds to run. On an input of size 750, the algorithm takes 81 seconds to run. What is the value of k?

The value of k is 4

Explanation:

Solution

Given that:

k = integer

Input size = 500

The algorithm takes a run of = 16 seconds

Input size = 750

The algorithm takes a run of = 81 seconds

Now,

We have to determine the value of k

The equation is shown below:

(500) ^k / 16 = (750) ^k / 81

Thus

(750/500) ^ k = 81/16

= (3/2) ^k

= (3/2) ^ 4

k is = 4