Question

Suppose an algorithm A₁ has a runtime T₁(n) defined ( in seconds) by the following function

T₁(n) = n³ + 20n + 15

For n = 13, the runtime of the algorithm is 2472 seconds. Let us assume that we have an algorithm A₂ with runtime given by T₂(n) = n² + 22n + 14? What will be the lowest value of n for which the runtime of A₂ exceeds 2472 seconds?

**Urgently needed**

Answer 1

To find a value of T₂(n) = n² + 22n + 14 in such a way that it exceeds 2472 seconds, following steps are to be done:

Step 1: Take  n² + 22n + 14 = 2472 and find the value of n. This is to be done as on substituting the value of n the result shouls be more than 2472. So fist find the value of n for which T₂(n) = 2472.

so,    n² + 22n + 14 = 2472

=>  n² + 22n + 14 - 2472 = 0

=> n² + 22n -2458 = 0

Now use discriminant method to solve the equation: any equation is of the form ax² + by +c =0

D = sqroot(b²-4*a*c) = sqroot((22)² - 4*1*(-2458)) = 101.56 = positive

Hence, value of n exists.

so, n = (-b D) / 2*a

n = (-22 101.56) / 2 *1

on solving n = 39.78 and -61.78

negative value of n is not acceptable. So n = 39.78. To get the lowest n approximate it to 40.

Step 2 :

The value should come out to be more than 2472. so put the value as 40.

So, T₂(n) = n² + 22n + 14 = (40)² + 22*40 + 14 = 2494.

Answer : Therefore lowest possible value of n =40.